SU-CS254 FEB032025 — Jemoka Knowledge Base

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\left(x, w_{1}, w_{2}\right) = 1 \end{equation}

We can define:

\begin{equation} \left(x, w_{1}\right) \in L’ \Leftrightarrow \forall w_{2} V\left(x, w_{2}, w_{2}\right) = 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\left(x, w_{1}\right) = 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}}\left(x, w_{1}\right) = 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 See Oracle Turing Machine Oracle Turing Languages \begin{equation} \text{P}^{\text{SAT}} : \left{L : L\text{ can be decided in polytime with SAT-oracle TM}\right} \end{equation} generally…

\begin{equation} \left\{\text{NP}, \text{P}, \text{coNP}\right\} \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\left(x, w_1, w_2\right) = 1. tangent, why can’t we place A into \Sigma_{1}? Say we desire A accepts x \Leftrightarrow \exists w, V\left(x, w\right) = 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} \left(b_1, \dots, b_{m}\right) \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\left(x, w_1, w_2\right) = 1 \end{equation}

Let’s write certificates: the oracle anwsers + the “satisfying assignment” certificate

\begin{equation} w_1 = \left\{\left(b_1, \dots, b_{m}\right), \forall i \text{ s.t. } b_{i} = 1, \text{ give } z_{i}: \phi_{i} \left(z_{i}\right) = 1\right\} \end{equation}

and the “unsatisfying assignment” certificate

\begin{equation} w_2 = \left\{\forall i \text{ s.t. } b_{i} = 0, z_{i}\text{ s.t. } \phi_{i}\left(z_{i}\right) = 0\right\} \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} \left(z_{i}\right) = 1; reject if not if b_{i} = 0, check if \phi_{i} \left(z_{i}\right) = 0, reject if not if b_{i} passes check, then use b_{i} as an answer accept iff A accepts