Random CNF's are hard for the polynomial calculus

DOI10.1007/s00037-010-0293-1zbMath1216.03064OpenAlexW2139212134MaRDI QIDQ626686

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

Gröbner basislower boundspolynomial calculuspropositional proof complexitycomplexity of refuting unsatisfiable systems of linear equationsGaussian widthrandom CNF formulaerefutation-degree

Mathematics Subject Classification ID

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

Related Items (14)

Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ Space Complexity in Polynomial Calculus ⋮ Sharp Effective Finite-Field Nullstellensatz ⋮ Unnamed Item ⋮ Towards NP-P via proof complexity and search ⋮ Algebraic proofs over noncommutative formulas ⋮ Unnamed Item ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Linear gaps between degrees for the polynomial calculus modulo distinct primes ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ Propositional proof complexity ⋮ Unnamed Item ⋮ Unnamed Item

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