Diagonalization in proof complexity
From MaRDI portal
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
(10)- The Complexity of the Diagonal Problem for Recursion Schemes
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- Substitutions into propositional tautologies
- Nisan-Wigderson generators in proof systems with forms of interpolation
- A proof complexity generator
- INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
- Iterated lower bound formulas: a diagonalization-based approach to proof complexity
- ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
- On meta complexity of propositional formulas and propositional proofs
- Diagonalisation and Church's Thesis: Kleene's Homework
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)