Author: Jan Krajicek
Publisher: Cambridge University Press
Keywords: encyclopedia, mathematics, applications, theory, complexity, arithmetic, propositional, logic, bounded
Number of Pages: 360
Published: 1995-11-24
List price: $158.00
ISBN-10: 0521452058
ISBN-13: 9780521452052

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 is followed by discussion of important results in propositional proof systems and systems of bounded arithmetic. Then more advanced topics are treated, including polynomial simulations and conservativity results, various witnessing

Authors:Peter Clote, Jan Krajícek,
Publisher: Oxford University Press, USA
Keywords: oxford, logic, guides, complexity, computational, proof, theory, arithmetic
Number of Pages: 448
Published: 1993-06-10
List price: $199.00
ISBN-10: 0198536909
ISBN-13: 9780198536901

This book principally concerns the rapidly growing area of what might be termed "Logical Complexity Theory": the study of bounded arithmetic, propositional proof systems, length of proof, and similar themes, and the relations of these topics to computational complexity theory. Issuing from a two-year international collaboration, the book contains articles concerning the existence of the most general unifier, a special case of Kreisel’s conjecture on length-of-proof, propositional logic proof size, a new alternating logtime algorithm for boolean formula evaluation and relation to branchin