A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
From MaRDI portal
Publication:2944868
DOI10.1090/S0002-9939-2015-12610-XzbMath1371.03091arXiv1311.2501MaRDI QIDQ2944868
Publication date: 8 September 2015
Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.2501
proof complexity\(\mathrm{AC}^0[p\) Frege systems]constant depth Frege systems
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Cites Work
- Exponential lower bounds for the pigeonhole principle
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Lower bounds for the polynomial calculus
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- The independence of the modulo p counting principles
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Parity, circuits, and the polynomial-time hierarchy
- The relative efficiency of propositional proof systems
- Lower bounds to the size of constant-depth propositional proofs
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- On the degree of ideal membership proofs from uniform families of polynomials over a finite field
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
