ECCC-Report TR02-003https://eccc.weizmann.ac.il/report/2002/003Comments and Revisions published for TR02-003en-usTue, 08 Jan 2002 16:29:42 +0200
Paper TR02-003
| A Gap in Average Proof Complexity |
Eli Ben-Sasson,
Yonatan Bilu
https://eccc.weizmann.ac.il/report/2002/003We present the first example of a natural distribution on instances
of an NP-complete problem, with the following properties.
With high probability a random formula from this
distribution (a) is unsatisfiable,
(b) has a short proof that can be found easily, and (c) does not have a short
(general) resolution proof. This happens already for a very low
clause/variable density ratio
of $\Delta = \log n$ ($n$ is the number of variables). This is
the first
example of such a natural distribution for which general resolution
proofs are not the best way for proving unsatisfiability of random
instances. Our result gives
hope that efficient proof methods might be found for random 3-CNFs
with small clause density (significantly less than $\sqrt{n}$).
Tue, 08 Jan 2002 16:29:42 +0200https://eccc.weizmann.ac.il/report/2002/003