Random CNF's are hard for the polynomial calculus

DOI10.1007/S00037-010-0293-1MaRDI QIDQ626686zbMATHOpenAlexFDO

Authors Eli Ben-Sasson, Russell Impagliazzo

Publication date 18 February 2011

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-010-0293-1

zbMATH Keywords

[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Gr%EF%BF%BD%EF%BF%BDbner+basis&go=Go Gr��bner basis]lower boundspropositional proof complexitycomplexity of refuting unsatisfiable systems of linear equationsGaussian widthpolynomial calculusrandom CNF formulaerefutation-degree

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Classical propositional logic (03B05) Complexity of proofs (03F20)

Recommendations

• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Publication:3031835
• Publication:4542576
• Counting solutions to random CNF formulas
• On random hard sets for NP
• Publication:4525683
• Publication:4723714
• A Note on Randomized Polynomial Time
• Publication:4942045
• Publication:4520323

Cited in

(18)

• Algebraic proofs over noncommutative formulas
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• A framework for space complexity in algebraic proof systems
• Sharp Effective Finite-Field Nullstellensatz
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• Towards NP-P via proof complexity and search
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Short propositional refutations for dense random 3CNF formulas
• A generalized method for proving polynomial calculus degree lower bounds
• scientific article; zbMATH DE number 7471677 (Why is no real title available?)
• scientific article; zbMATH DE number 7029312 (Why is no real title available?)
• Propositional proof complexity
• Space Complexity in Polynomial Calculus
• Size, cost and capacity: a semantic technique for hard random QBFs
• scientific article; zbMATH DE number 2174386 (Why is no real title available?)
• Optimality of size-degree tradeoffs for polynomial calculus
• Random resolution refutations

This page was built for publication: Random CNF's are hard for the polynomial calculus

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