Suggest edit — SU-CS254 FEB032025

Title

Name

Note

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