A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
From MaRDI portal
Publication:2944868
\(\mathrm{AC}^0[p\) Frege systems]constant depth Frege systemsproof complexity
Abstract: We give a general reduction of lengths-of-proofs lower bounds for constant depth Frege systems in DeMorgan language augmented by a connective counting modulo a prime (the so called Frege systems) to computational complexity lower bounds for search tasks involving search trees branching upon values of maps on the vector space of low degree polynomials over the finite filed with elements.
Recommendations
- The polynomial bounds of proof complexity in Frege systems
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- scientific article; zbMATH DE number 1361469
- Theories for subexponential-size bounded-depth Frege proofs
- A finite-model-theoretic view on propositional proof complexity
- Proof Complexity of the Cut-free Calculus of Structures
- Upper bounds on complexity of Frege proofs with limited use of certain schemata
- On a method for proving exact bounds on derivational complexity in Thue systems
- Proof complexity of intuitionistic implicational formulas
- Reduction of provability logics to _1-provability logics
Cites work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Exponential lower bounds for the pigeonhole principle
- scientific article; zbMATH DE number 5845490 (Why is no real title available?)
- scientific article; zbMATH DE number 176196 (Why is no real title available?)
- scientific article; zbMATH DE number 1215500 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1114017 (Why is no real title available?)
- scientific article; zbMATH DE number 1114025 (Why is no real title available?)
- scientific article; zbMATH DE number 2079024 (Why is no real title available?)
- scientific article; zbMATH DE number 1361469 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- Lower bounds for the polynomial calculus
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Lower bounds to the size of constant-depth propositional proofs
- On the degree of ideal membership proofs from uniform families of polynomials over a finite field
- Parity, circuits, and the polynomial-time hierarchy
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- The independence of the modulo \(p\) counting principles
- The relative efficiency of propositional proof systems
Cited in
(5)- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Exponential lower bounds for \(\mathrm{AC}^{0}\)-Frege imply superpolynomial Frege lower bounds
- scientific article; zbMATH DE number 1559592 (Why is no real title available?)
- Some subsystems of constant-depth Frege with parity
- Extended Nullstellensatz proof systems
This page was built for publication: A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944868)
