## 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"

http://www.infography.com/content/052906182153.html

© 2009 Fields of Knowledge

Essex, Iowa 51638-4608 USA