# Rigorous definition of efficient algorithm that $\epsilon$-refutes random 3CNF formulas

I recently asked a similar question, 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:

The problem of refuting random 3CNF concerns efficient algorithms that provide a proof that a random 3CNF is not satisfiable, or far from being satisfiable. This can be thought of as a game between an adversary and an algorithm. The adversary should produce a 3CNF formula. It can either produce a satisfiable formula, or produce a formula uniformly at random. The algorithm should identify whether the produced formula is random or satisfiable.

Formally, let $$\Delta\colon \mathbb N \to \mathbb N$$ and $$0 \leq \epsilon < \frac14$$. We say that an efficient algorithm $$A$$ $$\epsilon$$-refutes random 3CNF with ratio $$\Delta$$ if its inputs is $$\phi \in \mathrm{3CNF}_{n,n\Delta(n)}$$, its output is either "typical" or "exceptional", and it satisfies:

• Soundness: If $$\operatorname{Val}(\phi) \ge 1-\epsilon$$ then $$\Pr_{\text{Rand. coins of A}}(A(\phi)=\text{"exceptional"}) \geq \frac34.$$

• Completeness: For every $$n$$, $$\Pr_{\substack{\text{Rand. coins of A}\\ \phi \sim \operatorname{Uni}(\mathrm{3CNF}_{n,n\Delta(n)})}}(A(\phi)=\text{"typical"}) \geq 1 - o(1).$$ By a standard repetition argument, the probability of $$\frac34$$ can be amplified to $$1-2^{-n}$$, while efficiency is preserved. Thus, given such an (amplified) algorithm, if $$A(\phi)=\text{"typical"}$$, then with confidence of $$1-2^{-n}$$ we know that $$\operatorname{Val}(\phi) < 1-\epsilon$$. Since for random $$\phi \in \mathrm{3CNF}_{n,n\Delta(n)}$$, $$A(\phi)=\text{"typical"}$$ with probability $$1-o(1)$$, such an algorithm provides, for most 3CNF formulas, a proof that their value is less than $$1-\epsilon$$.

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 don't 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 $$\operatorname{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 it's 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?

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

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.

• I vote we rename this the "Florida Voting Algorithm" – Luke Mathieson May 11 '15 at 7:59
• 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) – vzn May 11 '15 at 15:19
• @vzn This condition is actually not necessary. The algorithm has no incentive to vote otherwise. – Yuval Filmus May 11 '15 at 15:25
• 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. – Charlie Parker May 11 '15 at 19:38
• 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/…. – Yuval Filmus May 11 '15 at 19:42