Bounded Arithmetic, Propositional Logic and Complexity Theory

ISBN: 9780511884283 出版年：1995 页码：361 Jan Krajicek Cambridge University Press

1. Introduction 2. Preliminaries 3. Basic complexity theory 4. Basic propositional logic 5. Basic bounded arithmetic 6. Definability of computations 7. Witnessing theorems 8. Definability and witnessing in second order theories 9. Translations of arithmetic formulas 10. Finite axiomatizability problem 11. Direct independence proofs 12. Bounds for constant-depth Frege systems 13. Bounds for Frege and extended Frege systems 14. Hard tautologies and optimal proof systems 15. Strength of bounded arithmetic References Index.