Suggest edit — Oracle Polynomial Time

Title

Name

Note

---
title: "Oracle Polynomial Time"
type: concept
related: [Oracle Polynomial Time]
source: https://www.jemoka.com/posts/kbhoracle_polynomial_time/
confidence: high
status: active
---

Recall: Oracle Turing Machines is a machine which has oracle $B \subseteq \Gamma^{*}$ which lets you ask &ldquo;if $z \in B$, then do something, otherwise do something else&rdquo; and check that in ONE STEP.
We have:
\begin{equation} P^{B} = \qty {L \mid L \text{{ can be decided by a polynomial-time TM with oracle for $B$ }}} \end{equation}
For example $P^{\text{SAT}}$ are languages we can decide in polynomial time once we have an oracle in SAT, and $P^{\text{NP}}$ are languages decidable by some Oracle Polynomial Time $TM$ for some $B \in NP$.
Notice that $P^{\text{NP}} \subseteq P^{\text{SAT}}$ because whenever we want to query the oracle $NP$ we first poly-reduce it to SAT, then ask SAT. This doesn&rsquo;t leave poly-time for the loop-up step.
some examples Polynomial Oracles We know that $P^{P} \subseteq P$ (this is because instead of looking up the oracle, we can just do it ourselves in poly-time)
Non-Polynomial Oracles We also know that $NP \subseteq P^{NP}$, because for $L \in NP$, we can just solve it in NP by guessing every input and checking with our oracle in one step.
CoNP Oracles Also, $\text{coNP} \subseteq P^{\text{NP}}$, we can ask the oracle for the answer, and then negate it. By definition, since $\neg L \in \text{NP}$ for $L \in \text{coNP}$, we can simply solve a language $\in \text{coNP}$ by querying the oracle for the corresponding NP language and then reverse it
Open Questions \begin{equation} NP =^{?} NP^{\text{NP}} \end{equation}
\begin{equation} \text{coNP} =^{?} NP^{NP} \end{equation}
Logic Minimization Suppose two boolean formulas $\phi$ and $\psi$ over the variables $x_1, &hellip;, x_{n}$ if they have the same value on every assignment of variables (that is, ever assignment that satisfies $\phi$ using $x_{j}$ choices also satisfies $\psi$ with the same $x_{j}$ choices).
A Boolean formula $\phi$ is minimal if there are no smaller formulas equivalent to $\phi$.
\begin{equation} \text{{MIN-FORMULA}} = \qty {\phi \mid \phi \text{{ is min }}} \end{equation}
Proof:
Let&rsquo;s define:
\begin{equation} \text{NEQUIV} = \qty {(\phi, \psi) \mid \phi, \psi \text{ not equivalent }} \end{equation}
in particular, $\text{NEQIV} \in NP$ because to check if something is in $\text{NEQIV}$ we simply has to guess all assignments and check if any of them are not equivalent.
Now, we can solve $\text{MIN-FORMULA}\in \text{coNP}^{\text{NEQIV}}$ because, given a formula $\phi$, we try all the $\psi$ smaller than $\phi$. If every $(\phi, \psi) \in \text{NEQIV}$, accept. Otherwise, reject.