3
$\begingroup$

Intuitively, recall what 3CNF formulas mean:

Its a boolean formula with conjunctive normal form (i.e. formula of ANDs of clauses with ORs) with no more than three variables per conjunct.

I was reading a paper that said:

under a widely believed assumption that refuting random 3CNF formulas is hard, it is impossible to efficiently learn this class using ony $O(\frac{n}{\epsilon^2})$ examples.

however, I wasn't sure what "refuting random 3CNF formulas" even meant so I was having a hard time understanding the sentence. Someone know what that means?

$\endgroup$
  • $\begingroup$ see also research on the "SAT transition pt". alas there is not yet a good wikipedia article on the subj :( $\endgroup$ – vzn May 10 '15 at 18:46
5
$\begingroup$

A random 3CNF with $n$ variables and $m$ clauses is obtained by picking $m$ clauses uniformly at random among the $8\binom{n}{3}$ different clauses. It is known that there exists a constant $C$ such that when $m = Cn$, a random 3CNF is unsatisfiable with high probability; it is strongly suspected that there exists a best such constant $C$, which is known experimentally to be about $4.2$.

It seems, therefore, that if I give you a random 3CNF with $n$ variables and $100n$ clauses, it should be easy to prove that it's unsatisfiable (unless you're very unlucky). However, the best such algorithm, due to Feige and Ofek, only works for $m = \Omega(n^{1.5})$. The best non-deterministic algorithm, due to Feige, Kim and Ofek, only works for $m = \Omega(n^{1.4})$.

One can state many conjectures of the form "refuting random 3CNF formulas is hard". The weakest would state that for every $C > 0$, there is no polynomial time algorithm that, given a formula, answers either unsatisfiable or don't know, and (i) answers unsatisfiable with high probability when given a random 3CNF with $n$ variables and $Cn$ clauses, (ii) answers unsatisfiable only for unsatisfiable formulas.

Stronger conjectures would work for $n^{1+\epsilon}$ clauses for some $\epsilon > 0$, and for non-deterministic polynomial time algorithms.

$\endgroup$
  • $\begingroup$ so refuting a 3CNF formula is a statement wether there is an algorithm that can conclude wether the formula is satisfiable or not? $\endgroup$ – Charlie Parker May 9 '15 at 22:11
  • 1
    $\begingroup$ Not exactly. The algorithm should either declare "unsatisfiable" or "don't know", but most of the time it should declare "unsatisfiable", and it should never be wrong. $\endgroup$ – Yuval Filmus May 9 '15 at 22:12
  • 1
    $\begingroup$ It's not a rigorous term, but when they mention a "widely believed assumption", they assume that you know what they're talking about, that is, there is a precise rigorous conjecture which is known as "refuting random 3CNF formulas is hard"; compare, for example, the "unique games conjecture". They should probably have cited some source stating this conjecture, for the sake of the coming generations, since in the future this conjecture might have a different name (or even be a theorem!). $\endgroup$ – Yuval Filmus May 9 '15 at 22:19
  • 1
    $\begingroup$ Variables can appear positively or negatively. $\endgroup$ – Yuval Filmus May 9 '15 at 22:25
  • 1
    $\begingroup$ The algorithm should never say unsatisfiable for a satisfiable instance. Refuting a random 3CNF when $m = 100n$ should be hard. Current algorithms only handle $m = \Omega(n^{1.5})$ (deterministic) and $m = \Omega(n^{1.4})$ (non-deterministic), which have many more clauses. $\endgroup$ – Yuval Filmus May 9 '15 at 23:50
3
$\begingroup$

I want to add some remarks that helped me understand (conceptually) much better what "refuting 3CNF" formulas meant (and thanks Yuval, his answer and discussion was useful, make sure you read it!).

First, want to point out what refuting means (this might have been an important (but easy to fix), confusion for me since English isn't my first language), Refuting means:

prove (a statement or theory) to be wrong or false.

i.e. in the context of satisfiability, determining wether a formula is false (or unsatisfiable) is the same thing as refuting the (boolean) formula.

Hence, in this context, an algorithm A that refutes a random 3CNF (3-conjunctive normal form) formula means that the algorithm is able to determine wether the boolean formula is unsatisfiable or "it doesn't know".

A useful extract of the paper I am reading discusses this more precisely on page 5. For reference here is a screen shot of that discussion:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.