1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Command Master
    Commented May 2, 2023 at 3:23
  • 1
    $\begingroup$ @CommandMaster Oh, that is true. So Oracle-SAT necessarily cannot reduce to SAT then. $\endgroup$
    – Loic Stoic
    Commented May 2, 2023 at 3:32

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.