Diagonalization in proof complexity

DOI10.4064/FM182-2-7MaRDI QIDQ4829363zbMATH OpenOpenAlexFDO

Authors Jan Krajíček

Publication date 29 November 2004

Published in Fundamenta Mathematicae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4064/fm182-2-7

zbMATH Keywords

propositional proof system

Mathematics Subject Classification ID

Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The Complexity of Diagonalization
• Diagonalizations over polynomial time computable sets
• scientific article; zbMATH DE number 4121422
• The Complexity of the Diagonal Problem for Recursion Schemes
• scientific article; zbMATH DE number 1302386
• Diagonalization strikes back: some recent lower bounds in complexity theory
• Iterated lower bound formulas: a diagonalization-based approach to proof complexity
• Provability, mechanism, and the diagonal problem
• scientific article; zbMATH DE number 1507040

Cited in

(13)

• ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
• Nisan-Wigderson generators in proof systems with forms of interpolation
• A proof complexity generator
• INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
• The Complexity of the Diagonal Problem for Recursion Schemes
• Diagonalisation and Church's Thesis: Kleene's Homework
• Iterated lower bound formulas: a diagonalization-based approach to proof complexity
• ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
• From proof complexity to circuit complexity via interactive protocols
• A proof complexity conjecture and the incompleteness theorem
• Iterated lower bound formulas: a diagonalization-based approach to proof complexity
• Substitutions into propositional tautologies
• On meta complexity of propositional formulas and propositional proofs

This page was built for publication: Diagonalization in proof complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4829363)