TR02-003 Authors: Eli Ben-Sasson, Yonatan Bilu

Publication: 8th January 2002 16:29

Downloads: 1858

Keywords:

We 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}$).