Initial segments of:

- Computers and Intractability by M. Garey and D. Johnson (Freeman Press, 1979)
- Complexity: Knots, Colouring and Counting by D. Welsh (London Math Soc. Lecture Notes 186, Cambridge University Press, 1993)

Dipping through one of the following:

- Automata and Computability or The Design and Analysis of Algorithms by D. Kozen (Springer-Verlag, 1997 and 1991)
- The Theory of Computation by B. Moret (Addison-Wesley, 1998)

Standard texts:

- Computers and Intractability

M. Garey and D. Johnson

Freeman Press

- Introduction to Automata Theory, Languages and Computation

J. Hopcroft and J. Ullman

Addison-Wesley

(Chapters 12-13)

Three survey chapters by the speaker:

- (1)"Complexity Classes"

(2)"Reducibility and Completeness"

(3) "Other Complexity Classes and Measures"

by Eric Allender, Michael Loui, Kenneth Regan

in the CRC Handbook of Algorithms and Theory of Computation

ed. M. Atallah

CRC Press

(Chapters available at www.cs.rutgers.edu/~allender/publications)

- Elwyn Berlekamp, John Conway, & Richard Guy: Winning
Ways, (vols I & II)

Academic Press, 1982

Especially recommended: Chapters 1,2,3,6. - Richard Nowakowski, ed: Games of No Chance

Cambridge U. Press, 1996

Especially recommended: Pages 365-405 - Elwyn Berlekamp & David Wolfe: Mathematical
Go

AK Peters, Ltd, 1994

Japanese translation by Yoshigawa published by Toppan

- Complexity and Real Computation

L. Blum, F. Cucker, S. Shub, and S. Smale

Springer-Verlag, 1998

Survey papers, available at http://www.mcs.vuw.ac.nz/research/maths-pubs.shtml:

- "Parameterized Complexity After (Almost) 10 Years: Review and Open
Questions"

Downey and Fellows - "Computational Tractability: The View From Mars"

Downey, Fellows, and Stege - "Parameterized Complexity: A Framework for Systematically Confronting
Computational Intractability"

Downey, Fellows, and Stege

Monograph:

- Parameterized Complexity

Downey and Fellows

Springer, 1999

- An Introduction to Kolmogorov Complexity and Its
Applications by Li
and Vitanyi

Springer-Verlag, 1997.

- B. Hartley and T. O. Hawkes: Rings, Modules and Linear
Algebra

Chapman and Hall, 1970

Chapter 11 (Linear transformations, matrices and canonical forms). - The speaker's survey chapter "Primitive prime divisor elements in
finite classical groups"

in Groups St Andrews 1997 in Bath, II

Eds. C. M. Campbell, E. F. Robertson, N. Ruskuc and G. C. Smith

London Math. Soc. Lecture Note Series 261 (1999)

pp. 605-623.

- Computers and Intractability

Garey and Johnson

Freeman Press

especially section 7.3 - Computational Complexity

Papadimitriou

Addison-Wesley

especially chapters 11 and 18 - Complexity: Knots, Colouring and Counting

Welsh

London Math Soc. Lecture Notes 186

Cambridge University Press