Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with random 3SAT:
TR11-006 | 20th January 2011
Sebastian Müller, Iddo Tzameret

Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas

Revisions: 1

Separating different propositional proof systems---that is, demonstrating that one proof system cannot efficiently simulate another proof system---is one of the main goals of proof complexity. Nevertheless, all known separation results between non-abstract proof systems are for specific families of hard tautologies: for what we know, in the average case all ... more >>>

ISSN 1433-8092 | Imprint