Random CNF's are hard for the polynomial calculus

DOI10.1007/S00037-010-0293-1zbMATH Open1216.03064OpenAlexW2139212134MaRDI QIDQ626686FDOQ626686

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

Recommendations

• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Publication:3031835
• scientific article; zbMATH DE number 1775444
• Counting solutions to random CNF formulas
• On random hard sets for NP
• scientific article; zbMATH DE number 1555920
• scientific article; zbMATH DE number 3995648
• A Note on Randomized Polynomial Time
• Publication:4942045
• scientific article; zbMATH DE number 1542868

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)

Cited In (18)

• Title not available (Why is that?)
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• Towards NP-P via proof complexity and search
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Short propositional refutations for dense random 3CNF formulas
• A generalized method for proving polynomial calculus degree lower bounds
• Sharp Effective Finite-Field Nullstellensatz
• Space Complexity in Polynomial Calculus
• Propositional proof complexity
• Algebraic proofs over noncommutative formulas
• Random resolution refutations
• A framework for space complexity in algebraic proof systems
• Title not available (Why is that?)
• Optimality of size-degree tradeoffs for polynomial calculus
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution

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)