Title :
Random CNFs are hard for the polynomial calculus
Author :
Ben-Sasson, Eli ; Impagliazzo, Russell
Author_Institution :
Inst. of Math. & Comput. Sci., Hebrew Univ., Jerusalem, Israel
Abstract :
We show a general reduction that derives lower bounds on degrees of polynomial calculus proofs of tautologies, over any field of characteristic (other than 2) from lower bounds for resolution proofs of a related set of linear equations module 2. We apply this to derive linear lower bounds on the degrees of PC proofs of randomly generated tautologies
Keywords :
computability; computational complexity; random processes; theorem proving; PC proofs; general reduction; linear equations; linear lower bounds; module 2; polynomial calculus proofs; random CNFs; randomly generated tautologies; resolution proofs; Calculus; Chromium; Computer science; Concrete; Ear; Equations; Layout; Polynomials; Read only memory; Size measurement;
Conference_Titel :
Foundations of Computer Science, 1999. 40th Annual Symposium on
Conference_Location :
New York City, NY
Print_ISBN :
0-7695-0409-4
DOI :
10.1109/SFFCS.1999.814613
