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:
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?