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?
