---
title: "SU-CS254 FEB032025"
source: https://www.jemoka.com/posts/kbhsu_cs254_feb032025/
date: 2025-02-03
---

Key question: why is having a SAT oracle less powerful than \(\text{SAT} \in P\)? What&rsquo;s the role of a oracle?
with a SAT oracle&hellip; 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&rsquo; \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&rsquo;\).
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&hellip; Look at our definition about \(A\); if we only have a \(\text{SAT}\) oracle, we don&rsquo;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&rsquo;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 &hellip;because a magic box can&rsquo;t be easily encoded in a Cook-Levin Theorem formula (since there&rsquo;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}} : \qty {L : L\text{ can be decided in polytime with SAT-oracle TM}} \end{equation}
generally&hellip;
\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&rsquo;t we place \(A\) into \(\Sigma_{1}\)? Say we desire \(A\) accepts \(x\) \(\Leftrightarrow \exists w, V\qty(x, w) = 1\). Can&rsquo;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 &ldquo;witness is fine.&rdquo;
The problem is that unlike a normal verifier, the oracle machine gives full trust to the oracle&rsquo;s output; unlike a verifier, it trusts the oracle fully and hence can be fooled.
You may say &ldquo;hey, I can just include the for-real certificate along as well&rdquo;; this is fine and poly-time for the \(1\) cases, but for the \(0\) cases, we have to ship along the &ldquo;for all&rdquo; 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&rsquo;s write certificates:
the oracle anwsers + the &ldquo;satisfying assignment&rdquo; 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 &ldquo;unsatisfying assignment&rdquo; 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
