3
$\begingroup$

I recently asked a similar What does "refuting random 3CNF" formulas mean?, however, I'd like to address it in a more mathematically precise setting.

In that paper, on page 5, it talks about a rigorous definition of what it means to $\epsilon-$refute random 3CNF formulas. For that, I will provide a screenshot of the exact part I want to address:

enter image description here

The exact part I want to address is the properties soundness and completeness of the algorithms.

First, what does it mean that the output is "typical" or "exceptional"? I dont think the authors define that precisely. I am guessing from context, if the algorithm returns exceptional then it found a boolean formula that is unsatisfiable? Though I am just guessing from the definition of the word refute.

From the definition of $Val(\phi)$ (=the fraction of clauses that are satisfiable, so its 1 when the whole thing is satisfiable) I am assuming that if the algorithm is sound then if it returns an answer, then the answer must be correct (i.e. the formula must be unsatisfiable). However, from the definitions given, it seems that if the formula is nearly satisfiable, then it says with high probability (greater than 3/4) that its "exceptional" (whatever that means)?

For completeness, what that usually means for me is that, if there is a correct answer, then the algorithm will return it. In this case, if we give it a boolean formula, if its unsatisfiable, then it will say so. Thats what completeness usually means for me. In this case, the conditions given in the paper for completeness are hard for me to understand.

I think maybe the main source of confusion might be what the word "exceptional" and "typical" mean. My intuition says that most boolean formulas are unsatisfiable, so in fact, "exceptional" should mean satisfiable and "typical" means unsatisfiable? Which is kind of opposite of what a refuting algorithm would do in my head.

Anyway, anyone have any ideas of how to resolve this in a mathematically precise way?

$\endgroup$
  • $\begingroup$ there is a fairly simple proof (by symmetry) that for SAT in general there are exactly as many unsatisfiable formulas as satisfiable ones. $\endgroup$ – vzn May 11 '15 at 15:14
2
$\begingroup$

The words "exceptional" and "typical" have absolutely no formal meaning. Let's rephrase the definition using two other words, "Clinton" and "Bush".

We say that a (possibly randomized) algorithm $A$ $\epsilon$-refutes random 3CNF with ratio $\Delta$ if:

  1. Given a 3CNF formula $\varphi$ with $n$ variables and $\Delta n$ clauses such that a $1-\epsilon$ fraction of the clauses (at least) is satisfiable, the probability that $A(\varphi)$ outputs "Clinton" is at least 75%.

  2. With high probability, $A(\varphi)$ outputs "Bush" given a random 3CNF formula with $n$ variables and $\Delta n$ clauses.

What does the algorithm $A$ try to do? It tries to identify "Clinton" inputs, which are inputs that are at least $1-\epsilon$ satisfiable. At the same time, on a random input, which is with high probability not "Clinton", it should return "Bush". So it tries to separate the rare "Clinton" inputs from a random input.

$\endgroup$
  • 1
    $\begingroup$ I vote we rename this the "Florida Voting Algorithm" $\endgroup$ – Luke Mathieson May 11 '15 at 7:59
  • $\begingroup$ ok but needs to also include the condition as previously that the $A(\varphi)$ is either "clinton" or "bush"... (ps reminiscent of hilberts tables, chairs & beer mugs) $\endgroup$ – vzn May 11 '15 at 15:19
  • $\begingroup$ @vzn This condition is actually not necessary. The algorithm has no incentive to vote otherwise. $\endgroup$ – Yuval Filmus May 11 '15 at 15:25
  • $\begingroup$ I find it very confusing that the paper calls one case soundness and the other completeness. As far as I am concerned, I thought Soundness is supposed to mean that if an answered is returned, then the answer is correct. In this setting, I can't seem relate the definitions I knew with the ones the paper has. $\endgroup$ – Charlie Parker May 11 '15 at 19:38
  • 1
    $\begingroup$ Soundness and completeness usually refer to two different guarantees of your algorithm or proof system, one holding for No instances and the other holding for Yes instances. The guarantees are sometimes probabilistic. See for example the definition of a PCP: en.wikipedia.org/wiki/…. $\endgroup$ – Yuval Filmus May 11 '15 at 19:42

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.