Diagonalization in proof complexity
From MaRDI portal
Publication:4829363
DOI10.4064/fm182-2-7zbMath1068.03049MaRDI QIDQ4829363
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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03F20: Complexity of proofs
Related Items
Substitutions into propositional tautologies, 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, Nisan-Wigderson generators in proof systems with forms of interpolation