Computational Complexity and Mathematical Logic
The following sources are recommended by a professor whose research specialty is computational complexity.
· M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
· C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
· U. Schoning and R. Pruim. Gems of Theoretical Computer Science. Springer, 1998.
· S.R. Buss (ed.). Handbook of Proof Theory. Chapters I and II. North Holland, 1998.
· S.R. Buss. Bounded Arithmetic. Bibliopolis, 1986.
· J. Krajicek. Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge, 1995.
· I. Wegener. The Complexity of Boolean Functions. Wiley, 1987.
· P. Hajek and P. Pudlak. Metamathematics of First-Order Arithmetic. Chapter V. Springer, 1993.
· J. van Leeuwen (ed.). Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity. Chapter 2, by D.S. Johnson, and Chapter 14, by R. Bopanner and M. Sipser. MIT Press, 1990.
· A. Urquhart. The Complexity of Propositional Proofs. Bull Symbolic Logic, Vol 1, No. 4, Dec. 1995.
"The Infography about Computational Complexity and Mathematical Logic"
© 2009 Fields of Knowledge
Essex, Iowa 51638-4608 USA