# Classes with oracles forcing the caller to immediately accept (or reject)?

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.

• 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. Commented May 26, 2017 at 0:06
• 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. Commented May 26, 2017 at 1:15
• @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. Commented May 27, 2017 at 10:46
• @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 :) Commented May 27, 2017 at 10:48
• 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? ​ ​ ​ ​
– user6973
Commented May 27, 2017 at 10:57

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$.