Proof complexity in algebraic systems and bounded depth Frege systems with modular counting

DOI10.1007/BF01294258zbMath0890.03030OpenAlexW1968655942MaRDI QIDQ1377580

Alexander A. Razborov, Pavel Pudlák, Jan Krajíček, Russell Impagliazzo, Jiří Sgall, Samuel R. Buss

Publication date: 29 June 1998

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01294258

zbMATH Keywords

lower boundmodular countingFrege proof systemcounting principledegree of polynomialsNullstellensatz proof systempolynomial calculus proof system

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Structure of proofs (03F07) Complexity of proofs (03F20)

Related Items (23)

Discretely ordered modules as a first-order extension of the cutting planes proof system ⋮ Dual weak pigeonhole principle, Boolean complexity, and derandomization ⋮ Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds ⋮ Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems] ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Towards NP-P via proof complexity and search ⋮ Algebraic proof systems over formulas. ⋮ Propositional proofs and reductions between NP search problems ⋮ Algebraic proofs over noncommutative formulas ⋮ Unnamed Item ⋮ Uniformly generated submodules of permutation modules over fields of characteristic 0. ⋮ Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity ⋮ Linear gaps between degrees for the polynomial calculus modulo distinct primes ⋮ Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies ⋮ Complexity of Null- and Positivstellensatz proofs ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ Phase transition of multivariate polynomial systems ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Propositional proof complexity ⋮ Random resolution refutations ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling

Cites Work

• Exponential lower bounds for the pigeonhole principle
• The intractability of resolution
• Lower bounds for the polynomial calculus
• \(\text{Count}(q)\) does not imply \(\text{Count}(p)\)
• Some remarks on lengths of propositional proofs
• The independence of the modulo p counting principles
• Many hard examples for resolution
• Hard examples for resolution
• Approximation and Small-Depth Frege Proofs
• The relative efficiency of propositional proof systems
• Provability of the pigeonhole principle and the existence of infinitely many primes
• 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
• The Complexity of Propositional Proofs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Proof complexity in algebraic systems and bounded depth Frege systems with modular counting