1 option
Proof complexity generators / Jan Krajíček, Charles University, Prague.
Math/Physics/Astronomy Library QA9.54 .K723 2025
Available
- Format:
- Book
- Author/Creator:
- Krajíček, Jan, Author.
- Series:
- London Mathematical Society lecture note series ; 497.
- London Mathematical Society lecture note series ; 497
- Language:
- English
- Subjects (All):
- Proof theory.
- Computational complexity.
- Physical Description:
- xii, 122 pages ; 23 cm.
- Place of Publication:
- Cambridge, United Kingdom ; New York, NY, USA : Cambridge University Press, 2025.
- Summary:
- "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.
- Contents:
- Introduction
- The dWPHP Problem
- [tau]-Formulas and Generators
- The Stretch
- Nisan-Wigderson Generator
- Gadget Generator
- The Case of ER
- Consistency Results
- Contexts
- Further Research
- τ-Formulas and Generators
- Notes:
- Includes bibliographical references (pages 114-119) and index.
- ISBN:
- 9781009611701
- 1009611704
- OCLC:
- 1473690643
The Penn Libraries is committed to describing library materials using current, accurate, and responsible language. If you discover outdated or inaccurate language, please fill out this feedback form to report it and suggest alternative language.