Key question: why is having a SAT oracle less powerful than \(\text{SAT} \in P\)? What’s the role of a oracle?
with a SAT oracle…
We can solve NP problems because SAT is NP complete; we can solve coNP problems we can now finally just negate it.
polynomial hierarchy collapses if \(\text{SAT} \in \text{P}\)
We can solve \(\Sigma_{j}\) because we can peel off inner languages; for instance, for \(\Sigma_{2}\):
\begin{equation} x \in L \Leftrightarrow \exists w_{1} \forall w_{2} V\qty(x, w_{1}, w_{2}) = 1 \end{equation}
We can define:
\begin{equation} \qty(x, w_{1}) \in L’ \Leftrightarrow \forall w_{2} V\qty(x, w_{2}, w_{2}) = 1 \end{equation}
since \(P = NP \implies P = coNP\), there exists a polytime \(A\) for \(L’\).
Therefore, \(x \in L \Leftrightarrow \exists w_1, A\qty(x, w_{1}) = 1\), so this is now in \(NP\), and we again have a polytime for it.
polynomial hierarchy against a \(\text{SAT}\) oracle…
Look at our definition about \(A\); if we only have a \(\text{SAT}\) oracle, we don’t have \(A \in \text{coNP} \implies A \in \text{P}\). This is because we actually have \(A \in \text{coNP} \implies A^{\text{SAT}} \in P\).
Yet, on the next step, we have
\(x \in L \Leftrightarrow \exists w_1, A^{\text{SAT}}\qty(x, w_{1}) = 1\)
Now, we can’t actually use or oracle again! What we want to do next is to show that the above stament implies that \(\text{L} \in \text{NP}\) and we can invoke Cook-Levin Theorem. Yet, this oracle use breaks Cook-Levin Theorem!
oracles break Cook-Levin theorem
…because a magic box can’t be easily encoded in a Cook-Levin Theorem formula (since there’s no tape delta that can be captured as a clause in the Cook-Levin Theorem reduction).
instead, we need to use the result in \(\text{P}^{\text{SAT}} \subseteq \Sigma_{2}\) to show that the oracle is slightly less powerful
Oracle Turing Machine
Oracle Turing Languages
\begin{equation} \text{P}^{\text{SAT}} : \qty {L : L\text{ can be decided in polytime with SAT-oracle TM}} \end{equation}
generally…
\begin{equation} \qty {\text{NP}, \text{P}, \text{coNP}} \in \text{P}^{\text{SAT}} \end{equation}
\(\text{P}^{\text{SAT}} \subseteq \Sigma_{2}\)
Suppose \(\text{L} \in \text{P}^{\text{SAT}}\), solved by some SAT oracle Turing Machine called \(A\).
We desire that \(A\) accepts \(x\) \(\Leftrightarrow\) \(\exists w_{1} \forall w_{2} V\qty(x, w_1, w_2) = 1\).
tangent, why can’t we place \(A\) into \(\Sigma_{1}\)? Say we desire \(A\) accepts \(x\) \(\Leftrightarrow \exists w, V\qty(x, w) = 1\). Can’t we feasibly make \(w\) contain all the oracle answers? In particular since \(A\) is a poly-oracle machine, it makes at most poly oracle calls, so the “witness is fine.”
The problem is that unlike a normal verifier, the oracle machine gives full trust to the oracle’s output; unlike a verifier, it trusts the oracle fully and hence can be fooled.
You may say “hey, I can just include the for-real certificate along as well”; this is fine and poly-time for the \(1\) cases, but for the \(0\) cases, we have to ship along the “for all” flavor certificates (think UNSAT).
This actually motivates our overall proof.
For:
\begin{equation} \qty(b_1, \dots, b_{m}) \text{ and } \begin{cases} b_{i} = 1, \text{proof $\phi_{i}$ \text{SAT}} \\ b_{i} = 0, \text{proof $\phi_{i}$ \text{UNSAT}} \end{cases} \end{equation}
So, we desire to make:
\begin{equation} \text{A} \text{ accept } x \Leftrightarrow \exists w_{1} \forall w_{2} V\qty(x, w_1, w_2) = 1 \end{equation}
Let’s write certificates:
the oracle anwsers + the “satisfying assignment” certificate
\begin{equation} w_1 = \qty {\qty(b_1, \dots, b_{m}), \forall i \text{ s.t. } b_{i} = 1, \text{ give } z_{i}: \phi_{i} \qty(z_{i}) = 1} \end{equation}
and the “unsatisfying assignment” certificate
\begin{equation} w_2 = \qty {\forall i \text{ s.t. } b_{i} = 0, z_{i}\text{ s.t. } \phi_{i}\qty(z_{i}) = 0} \end{equation}
given \(x, w_1, w_2\), our \(V\) will proceed as follows:
- simulate \(A\) on \(x\)
- when \(A\) makes its ith Oracle query, \(V\) looks up answer \(b_{i}\)
- if \(b_{i} = 1\), check if \(\phi_{i} \qty(z_{i}) = 1\); reject if not
- if \(b_{i} = 0\), check if \(\phi_{i} \qty(z_{i}) = 0\), reject if not
- if \(b_{i}\) passes check, then use \(b_{i}\) as an answer
- accept iff \(A\) accepts