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

DOI10.1007/BF01294258zbMATH Open0890.03030OpenAlexW1968655942MaRDI QIDQ1377580FDOQ1377580

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

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

Recommendations

• The polynomial bounds of proof complexity in Frege systems
• scientific article; zbMATH DE number 1114025
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• scientific article; zbMATH DE number 2196511
• Complexity of semialgebraic proofs with restricted degree of falsity
• Complexity of Semialgebraic Proofs with Restricted Degree of Falsity
• scientific article; zbMATH DE number 1916823
• scientific article; zbMATH DE number 2086404
• Theories for subexponential-size bounded-depth Frege proofs
• scientific article; zbMATH DE number 1070621

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (35)

• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
• Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
• Title not available (Why is that?)
• Towards NP-P via proof complexity and search
• Phase transition of multivariate polynomial systems
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Propositional proofs and reductions between NP search problems
• Title not available (Why is that?)
• Hard examples for the bounded depth Frege proof system
• Nullstellensatz size-degree trade-offs from reversible pebbling
• First-order reasoning and efficient semi-algebraic proofs
• Extended Nullstellensatz proof systems
• Complexity of Null- and Positivstellensatz proofs
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Characterizing Propositional Proofs as Noncommutative Formulas
• Propositional proof complexity
• Discretely ordered modules as a first-order extension of the cutting planes proof system
• Randomized feasible interpolation and monotone circuits with a local oracle
• Uniformly generated submodules of permutation modules over fields of characteristic 0.
• Approximation and Small-Depth Frege Proofs
• Algebraic proofs over noncommutative formulas
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• On the Complexity of Verifying Regular Properties on Flat Counter Systems,
• Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
• Title not available (Why is that?)
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Random resolution refutations
• Algebraic proof systems over formulas.
• Title not available (Why is that?)
• A framework for space complexity in algebraic proof systems
• On the degree of ideal membership proofs from uniform families of polynomials over a finite field
• A bounded arithmetic AID for Frege systems
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377580)