Proof Complexity Generators

"This book presents a state-of-the-art theory in the field of proof complexity, aiming to construct hard propositional tautologies needed to solve the P vs. NP problem in the negative. The theory is introduced step by step, starting with the historic background, and several potential new avenues of research are highlighted"-- Provided by publisher.

Table des matières

1. Introduction; 2. The dWPHP problem; 3. ¿-formulas and generators; 4. The stretch; 5. Nisan-Wigderson generator; 6. Gadget generator; 7. The case of ER; 8. Consistency results; 9. Contexts; 10. Further research; Special symbols; References; Index.

A propos de l'auteur

Jan Krajíček is Professor of Mathematical Logic at Charles University, Prague. A member of the Learned Society of the Czech Republic and the Academia Europaea, he has previously published three books with Cambridge University Press (1995, 2011 and 2019).

Détails du produit

• Auteurs: Krají&, Jan (Charles University Krajicek, Jan Krajíček
• Edition: Cambridge University Press ELT
• Langues: Anglais
• Format d'édition: Livre de poche
• Sortie: 31.07.2025
• EAN: 9781009611701
• ISBN: 978-1-0-0961170-1
• Pages: 134
• Thème: London Mathematical Society Lecture Note Series
• Catégories: Sciences naturelles, médecine, informatique, technique > Mathématiques > Bases; Algebra, MATHEMATICS / Logic, MATHEMATICS / Algebra / General, Mathematical theory of computation, Mathematical logic