patternMinor
Rigorous definition of efficient algorithm that $\epsilon$-refutes random 3CNF formulas
Viewed 0 times
definitionrandomefficientepsilonformulasalgorithmthat3cnfrefutesrigorous
Problem
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
-
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)
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
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
-
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)
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
Solution
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:
-
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%.
-
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.
We say that a (possibly randomized) algorithm $A$ $\epsilon$-refutes random 3CNF with ratio $\Delta$ if:
-
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%.
-
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.
Context
StackExchange Computer Science Q#42399, answer score: 2
Revisions (0)
No revisions yet.