Proof Complexity (Encyclopedia of Mathematics and its Applications)

✍ Scribed by Jan Krajíček

Publisher: Cambridge University Press
Year: 2019
Tongue: English
Leaves: 534
Series: Encyclopedia of Mathematics and its Applications
Category: Library

No coin nor oath required. For personal study only.

✦ Synopsis

Proof complexity is a rich subject drawing on methods from logic, combinatorics, algebra and computer science. This self-contained book presents the basic concepts, classical results, current state of the art and possible future directions in the field. It stresses a view of proof complexity as a whole entity rather than a collection of various topics held together loosely by a few notions, and it favors more generalizable statements. Lower bounds for lengths of proofs, often regarded as the key issue in proof complexity, are of course covered in detail. However, upper bounds are not neglected: this book also explores the relations between bounded arithmetic theories and proof systems and how they can be used to prove upper bounds on lengths of proofs and simulations among proof systems. It goes on to discuss topics that transcend specific proof systems, allowing for deeper understanding of the fundamental problems of the subject.

✦ Table of Contents

Cover
Front Matter
ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS
Proof Complexity
Copyright
Dedication
Contents
Preface
Acknowledgements
Introduction
Part I: Basic Concepts
1 Concepts and Problems
2 Frege Systems
3 Sequent Calculus
4 Quantified Propositional Calculus
5 Resolution
6 Algebraic and Geometric Proof Systems
7 Further Proof Systems
Part II: Upper Bounds
8 Basic Example of the Correspondence between
Theories and Proof Systems
9 The Two Worlds of Bounded Arithmetic
10 Up to EF via the . . . Translation
11 Examples of Upper Bounds and p-Simulations
12 Beyond EF via the || . . . || Translation
Part III: Lower Bounds
13 R and R-Like Proof Systems
14 LKd+1/2 and Combinatorial Restrictions
15 Fd and Logical Restrictions
16 Algebraic and Geometric Proof Systems
17 Feasible Interpolation: A Framework
18 Feasible Interpolation: Applications
Part IV: Beyond Bounds
19 Hard Tautologies
20 Model Theory and Lower Bounds
21 Optimality
22 The Nature of Proof Complexity
Bibliography
Special Symbols
Index

📜 SIMILAR VOLUMES

Proof Complexity (Encyclopedia of Mathem

📁 Proof Complexity (Encyclopedia of Mathematics and its Applications)

✍ Jan Krajíček 📂 Library 📅 2019 🏛 Cambridge University Press 🌐 English

Bounded Arithmetic, Propositional Logic

📁 Bounded Arithmetic, Propositional Logic and Complexity Theory (Encyclopedia of Mathematics and its Applications)

✍ Jan Krajicek 📂 Library 📅 1995 🏛 Cambridge University Press 🌐 English

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 ope

Bounded Arithmetic, Propositional Logic

📁 Bounded Arithmetic, Propositional Logic and Complexity Theory (Encyclopedia of Mathematics and its Applications)

✍ Jan Krajicek 📂 Library 📅 1995 🌐 English

Special Functions (Encyclopedia of Mathe

📁 Special Functions (Encyclopedia of Mathematics and its Applications)

✍ George E. Andrews, Richard Askey, Ranjan Roy 📂 Library 📅 1999 🏛 Cambridge University Press 🌐 English

Special functions, which include the trigonometric functions, have been used for centuries. Their role in the solution of differential equations was exploited by Newton and Leibniz, and the subject of special functions has been in continuous development ever since. In just the past thirty years se

Minkowski Geometry (Encyclopedia of Math

📁 Minkowski Geometry (Encyclopedia of Mathematics and its Applications)

✍ A. C. Thompson 📂 Library 📅 1996 🌐 English

This is a comprehensive treatment of Minkowski geometry. The author begins by describing the fundamental metric properties and the topological properties of existence of Minkowski space. This is followed by a treatment of two-dimensional spaces and characterizations of Euclidean space among normed s

Model Theory (Encyclopedia of Mathematic

📁 Model Theory (Encyclopedia of Mathematics and its Applications)

✍ Wilfrid Hodges 📂 Library 📅 2008 🌐 English

Professor Hodges emphasizes definability and methods of construction, and introduces the reader to advanced topics such as stability. He also provides the reader with much historical information and a full bibliography, enhancing the book's use as a reference.