<p>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.</p>

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

CC BY-SA 3.0
2017-06-04T19:48:31.577Z
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).
David Eppstein
CC BY-SA 3.0
2017-05-29T16:52:54.093Z
2017-05-29T16:52:54.093Z
Emil Jeřábek
<p>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.</p>

<p>However, what happens if the caller <em>must</em> 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, <em>but</em> 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.</p>

<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2017-05-26T00:06:10.953Z
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.
chazisop
CC BY-SA 3.0
2017-05-26T01:15:34.150Z
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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bh) in this regard.
Joshua Grochow
CC BY-SA 3.0
2017-05-27T10:46:48.753Z
@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.
dkaeae
CC BY-SA 3.0
2017-05-27T10:48:38.130Z
@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  :)
dkaeae
CC BY-SA 3.0
2017-05-27T11:30:06.867Z
@RickyDemer The oracle is stateless, so only if the input encodes the previous queries somehow.
dkaeae
CC BY-SA 3.0
2017-05-29T16:17:58.477Z
@Ricky Demer I suppose the "oracle forces" formulation was a bit misleading (I'll edit that shortly). Essentially it's irrelevant _who_ forces it; the point is the caller is _only_ allowed to calculate further in case the oracle doesn't,  e.g., answer "no" to the query.
dkaeae
<cc.complexity-theory><polynomial-hierarchy>
Classes with oracles forcing the caller to immediately accept (or reject)?
dkaeae
# Classes with oracles forcing the caller to immediately accept (or reject)?

(Asked by: username_0 on 2017-05-25)

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.

**Tags:** cc.complexity-theory, polynomial-hierarchy
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bh) in this regard.  
> **username_0**: @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.  
> **username_0**: @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  :)  
> **username_0**: @RickyDemer The oracle is stateless, so only if the input encodes the previous queries somehow.  
> **username_0**: @Ricky Demer I suppose the "oracle forces" formulation was a bit misleading (I'll edit that shortly). Essentially it's irrelevant _who_ forces it; the point is the caller is _only_ allowed to calculate further in case the oracle doesn't,  e.g., answer "no" to the query.  

---

## 1 answers

### Answer by username_3 on 2017-05-29. Score: 3

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

> **Comments:**
> **username_4**: 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).  

---

