# Does $\texttt{Oracle-SAT} \leq_T^P \texttt{SAT} \iff \texttt{P} \neq \texttt{NP}$, and is this possible?

The problem of Oracle-SAT is given below:

Given oracle query access to some machine, $$U$$ that has $$2^N$$ inputs, determine if there is an input such that the machine accepts.

This is very similar to the regular SAT problem. The only alteration in SAT is that we are given the structure of the circuit; i.e. the CNF formula.

Oracle-SAT is clearly intractable, as we would need to examine all $$2^N$$ inputs. And SAT is thought to also be intractable, as $$P \neq NP$$.

Is it possible for Oracle-SAT to reduce to SAT? I am using the notion of Cook-reduction here. If we had an oracle that solved SAT, could we also solve Oracle-SAT in Polynomial time?

If it possible for Oracle-SAT to reduce to SAT, then this would imply $$P \neq NP$$, right?

• How would a SAT oracle affect the fact we need to examine all $2^N$ inputs? It can't give you any information about the particular oracle you are accessing. May 2 at 3:23
• @CommandMaster Oh, that is true. So Oracle-SAT necessarily cannot reduce to SAT then. May 2 at 3:32

Oracle-SAT is not $$\leq_{\mathrm{T}}^P$$-reducible to any formal language $$L$$. The reason is that any such reduction would only be able to query the oracle $$U$$ on a polynomial number of inputs, in addition to the queries made to $$L$$. If $$U$$ returns "no" for all the inputs it is asked about, the correct answer could still be either "yes" or "no", however, the entire computation performed by the reduction (with access to $$L$$) would act in the very same way regardless.