Diagonalization in proof complexity

DOI10.4064/fm182-2-7zbMath1068.03049OpenAlexW2075488709MaRDI QIDQ4829363

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

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

Related Items (6)

Nisan-Wigderson generators in proof systems with forms of interpolation ⋮ Substitutions into propositional tautologies ⋮ INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH ⋮ ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ On meta complexity of propositional formulas and propositional proofs ⋮ ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION

This page was built for publication: Diagonalization in proof complexity