| Description |
1 online resource (xiv, 343 pages) |
| Series |
Encyclopedia of mathematics and its applications ; v. 60 |
|
Encyclopedia of mathematics and its applications ; v. 60.
|
| Contents |
7.7 Bibliographical and other remarks8 Definability and witnessing in second order theories; 8.1 Second order computations; 8.2 Definable functionals; 8.3 Bibliographical and other remarks; 9 Translations of arithmetic formulas; 9.1 Bounded formulas with a predicate; 9.2 Translation into quantified propositional formulas; 9.3 Reflection principles and polynomial simulations; 9.4 Model-theoretic constructions; 9.5 Witnessing and test trees; 9.6 Bibliographical and other remarks; 10 Finite axiomatizability problem; 10.1 Finite axiomatizability of Si2 and Ti2; 10.2 Ti2 versus Si2+1 |
|
10.3 Si2 versus Ti210.4 Relativized cases; 10.5 Consistency notions; 10.6 Bibliographical and other remarks; 11 Direct independence proofs; 11.1 Herbrandization of induction axioms; 11.2 Weak pigeonhole principle; 11.3 An independence criterion; 11.4 Lifting independence results; 11.5 Bibliographical and other remarks; 12 Bounds for constant-depth Frege systems; 12.1 Upper bounds; 12.2 Depth d versus depth d + 1; 12.3 Complete systems; 12.4 k-evaluations; 12.5 Lower bounds for the pigeonhole principle and for counting principles; 12.6 Systems with counting gates |
|
12.7 Forcing in nonstandard models12.8 Bibliographical and other remarks; 13 Bounds for Frege and extended Frege systems; 13.1 Counting in Frege systems; 13.2 An approach to lower bounds; 13.3 Boolean valuations; 13.4 Bibliographical and other remarks; 14 Hard tautologies and optimal proof systems; 14.1 Finitistic consistency statements and optimal proof systems; 14.2 Hard tautologies; 14.3 Bibliographical and other remarks; 15 Strength of bounded arithmetic; 15.1 Counting; 15.2 A circuit lower bound; 15.3 Polynomial hierarchy in models of bounded arithmetic |
| Summary |
This book presents an up-to-date, unified treatment of research in bounded arithmetic and complexity of propositional logic, with emphasis on independence proofs and lower bound proofs. The author discusses the deep connections between logic and complexity theory and lists a number of intriguing open problems. An introduction to the basics of logic and complexity theory is followed by discussion of important results in propositional proof systems and systems of bounded arithmetic. More advanced topics are then treated, including polynomial simulations and conservativity results, various witnessing theorems, the translation of bounded formulas (and their proofs) into propositional ones, the method of random partial restrictions and its applications, direct independence proofs, complete systems of partial relations, lower bounds to the size of constant-depth propositional proofs, the method of Boolean valuations, the issue of hard tautologies and optimal proof systems, combinatorics and complexity theory within bounded arithmetic, and relations to complexity issues of predicate calculus. Students and researchers in mathematical logic and complexity theory will find this comprehensive treatment an excellent guide to this expanding interdisciplinary area |
| Bibliography |
Includes bibliographical references (pages 327-334) and indexes |
| Notes |
Print version record |
| Subject |
Constructive mathematics.
|
|
Proposition (Logic)
|
|
Computational complexity.
|
|
MATHEMATICS -- General.
|
|
Computational complexity
|
|
Constructive mathematics
|
|
Proposition (Logic)
|
| Form |
Electronic book
|
| Author |
Cambridge University Press.
|
| ISBN |
9781107088634 |
|
1107088631 |
|
9780511529948 |
|
0511529945 |
|
