内容

目次

1. Introduction; 2. Preliminaries; 3. Basic complexity theory; 4. Basicpropositional logic; 5. Basic bounded arithmetic; 6. Definability ofcomputations; 7. Witnessing theorems; 8. Definability and witnessing insecond order theories; 9. Translations of arithmetic formulas; 10. Finiteaxiomatizability problem; 11. Direct independence proofs; 12. Bounds forconstant-depth Frege systems; 13. Bounds for Frege and extended Fregesystems; 14. Hard tautologies and optimal proof systems; 15. Strength ofbounded arithmetic; References; Index.