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.

List of contents

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.

About the author

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).

Product details

• Authors: Krají&, Jan (Charles University Krajicek, Jan Krajíček
• Publisher: Cambridge University Press ELT
• Languages: English
• Product format: Paperback / Softback
• Released: 31.07.2025
• EAN: 9781009611701
• ISBN: 978-1-0-0961170-1
• No. of pages: 134
• Series: London Mathematical Society Lecture Note Series
• Subjects: Natural sciences, medicine, IT, technology > Mathematics > Basic principles; Algebra, MATHEMATICS / Logic, MATHEMATICS / Algebra / General, Mathematical theory of computation, Mathematical logic