Oracle Polynomial Time — Jemoka Knowledge Base

Recall: Oracle Turing Machines is a machine which has oracle B \subseteq \Gamma^{*} which lets you ask “if z \in B, then do something, otherwise do something else” and check that in ONE STEP. We have:

\begin{equation} P^{B} = \left\{L \mid L \text{{ can be decided by a polynomial-time TM with oracle for $B$ }}\right\} \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’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, …, 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}} = \left\{\phi \mid \phi \text{{ is min }}\right\} \end{equation}

Proof: Let’s define:

\begin{equation} \text{NEQUIV} = \left\{(\phi, \psi) \mid \phi, \psi \text{ not equivalent }\right\} \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.