說明 
xiv, 516 pages ; 24 cm 

text txt rdacontent 

unmediated n rdamedia 

volume nc rdacarrier 
系列 
Encyclopedia of mathematics and its applications ; 170 

Encyclopedia of mathematics and its applications ; v. 170

附註 
Includes bibliographical references (pages 481505) and index 

Concepts and problems  Frege systems  Sequent calculus  Quantifed propositional calculus  Resolution  Algebraic and geometric proof systems  Further proof systems  Basic example of the correspondence  Two worlds of bounded arithmetic  Up to EF via the <...> translation  Examples of upper bounds and psimulations  Beyond EF via the  ...  translation  R and Rlike proof systems  LKD+1/2 and combinatorial restrictions  Fd and logical restrictions  Algebraic and geometric proof systems  Feasible interpolation: a framework  Feasible interpolation: applications  Hard tautologies  Model theory and lower bounds  Optimality  The nature of proof complexity 

"Proof complexity is a rich subject drawing on methods from logic, combinatorics, algebra and computer science. This selfcontained 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" Provided by publisher 
主題 
Proof theory


Computational complexity


Computational complexity. fast (OCoLC)fst00871991


Proof theory. fast (OCoLC)fst01078942

