Bounded arithmetic and propositional proof complexity
From MaRDI portal
Recommendations
Cited in
(37)- Bounded arithmetic for NC, ALogTIME, L and NL
- Bounded arithmetic, proof complexity and two papers of Parikh
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- On the bounded version of Hilbert's tenth problem
- Efficient rational proofs for space bounded computations
- Feasibly constructive proofs of succinct weak circuit lower bounds
- The scope of Gödel's first incompleteness theorem
- Partially definable forcing and bounded arithmetic
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- Expressivity of second order propositional modal logic
- Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Theories for subexponential-size bounded-depth Frege proofs
- scientific article; zbMATH DE number 5901621 (Why is no real title available?)
- scientific article; zbMATH DE number 5862941 (Why is no real title available?)
- scientific article; zbMATH DE number 424614 (Why is no real title available?)
- Polynomial induction and length minimization in intuitionistic bounded arithmetic
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Towards NP-P via proof complexity and search
- Witnessing functions in bounded arithmetic and search problems
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Circuit lower bounds in bounded arithmetics
- scientific article; zbMATH DE number 3995646 (Why is no real title available?)
- scientific article; zbMATH DE number 2102736 (Why is no real title available?)
- scientific article; zbMATH DE number 806753 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
- Logical foundations of proof complexity
- scientific article; zbMATH DE number 2196511 (Why is no real title available?)
- Fragments of bounded arithmetic and the lengths of proofs
- Mining the surface: witnessing the low complexity theorems of arithmetic
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- Witnessing flows in arithmetic
- On the unprovability of circuit size bounds in intuitionistic \(\mathsf{S}^1_2\)
- Provability of the circuit size hierarchy and its consequences
- Pure extensions, proof rules, and hybrid axiomatics
This page was built for publication: Bounded arithmetic and propositional proof complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4357061)
