Jan Krajicek (Prague Academy of Sciences of the Czech Republic)

Bounded Arithmetic, Propositional Logic and Complexity Theory

Herausgeber: Doran, B.; Rota, G. -C

• Gebundenes Buch

Produktbeschreibung

An up-to-date, unified treatment of research in this interdisciplinary subject, with emphasis on independence proofs and lower bound proofs. The author discusses the deep connections between logic and computational complexity theory and lists a number of intriguing open problems.

Produktdetails

• Encyclopedia of Mathematics and its Applications
• Verlag: Cambridge University Press
• Seitenzahl: 360
• Erscheinungstermin: 8. April 2004
• Englisch
• Abmessung: 235mm x 157mm x 26mm
• Gewicht: 672g
• ISBN-13: 9780521452052
• ISBN-10: 0521452058
• Artikelnr.: 21447551

Inhaltsangabe

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.