1
$\begingroup$

Usually an oracle operates as a black box, simply returning an yes or no answer to the machine calling it; once it has the result, the caller is free to proceed as it sees fit.

However, what happens if the caller must accept or reject (exactly one of the two) immediately as a function of the oracle's output? Say, for example, the caller has access to a SAT oracle, but must always accept (unconditionally) whenever the oracle answers with "yes"; this means the caller can continue its operation if and only if the query formula is unsatisfiable.

This imposes a restriction, obviously; are there cases in which this yields — or there is reason or evidence enough to suspect it yields — a strict subset of decision problems when compared to the "usual" behavior?

I am particularly interested in the case of $\mathsf{P}^{\mathsf{NP}}$ or similar classes in the polynomial hierarchy, but other classes and oracles are relevant too.

$\endgroup$
  • 3
    $\begingroup$ Many-one reductions essentially do what you describe. Without them, you cannot distinguish between NP and co-NP, since you can always "flip" the oracle's answer, so they are essential in studying the polynomial hierarchy. $\endgroup$ – chazisop May 26 '17 at 0:06
  • 6
    $\begingroup$ If you also allow sometimes reversing the answer of the oracle, you get what is called a "1-truth-table" or "1tt" reduction, which appears to be just slightly more powerful than many-one reductions, but still less powerful than full-on Turing reductions. You might be interested in the Boolean Hierarchy in this regard. $\endgroup$ – Joshua Grochow May 26 '17 at 1:15
  • 1
    $\begingroup$ @chazisop It's not quite a many-one reduction since the caller is allowed to continue its computation (on precisely one of the two accept/reject branches) once the oracle returns. $\endgroup$ – dkaeae May 27 '17 at 10:46
  • 1
    $\begingroup$ @JoshuaGrochow It's not quite a truth-table reduction (well, not at first sight); though I've managed to sketch a proof showing it's equivalent to it (at least in my special case). If you post the comment as an answer, I'll be happy to accept :) $\endgroup$ – dkaeae May 27 '17 at 10:48
  • $\begingroup$ Can the oracle's decision of whether-or-not it forces ​ "its caller to immediately enter an accept or reject state" ​ depend on prior queries too, or just on the current query? ​ ​ ​ ​ $\endgroup$ – user6973 May 27 '17 at 10:57
3
$\begingroup$

The question is not entirely clear to me. However, concerning the example that is spelled out more precisely: if a language is recognizable by a poly-time machine with a SAT oracle which must accept whenever the oracle answers “yes”, it is in fact in NP. First, observe that regardless of the oracle answers, we can simulate in polynomial time the only possible run of the algorithm by pretending all answers are “no”. (In particular, we can compute the list of all oracle queries beforehand.) Then, the original algorithm accepts iff one of the oracle answers in the simulated run is actually “yes”, or the simulated algorithm accepts in the end. This is an NP property.

More generally, if we use an arbitrary oracle $A$ in the above scenario in place of SAT, a language can be computed in the indicated way iff it is poly-time dtt-reducible to $A$.

$\endgroup$
  • $\begingroup$ Put another way, any algorithm in this model can be immediately transformed into an algorithm in a simpler model, one where you only ask a single question of a different oracle (the concatenation of the questions along the only possible run in the original model). $\endgroup$ – David Eppstein Jun 4 '17 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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