<p>Let's define what P<span class="math-container">$^A$</span> means in the promise setting: A language L is in P<span class="math-container">$^A$</span> if there is a polytime oracle machine <span class="math-container">$M$</span> such that for all sets <span class="math-container">$B$</span> such that <span class="math-container">$B$</span> contains <span class="math-container">$A_{YES}$</span> and <span class="math-container">$B\cap A_{NO}=\emptyset$</span>, <span class="math-container">$L=L(M^B)$</span>. In other words, the polytime machine can ask queries that are not part of the promise but its output cannot depend on whether those queries are answered yes or no.</p>
<p>For example, consider unique SAT where <span class="math-container">$A_{YES}$</span> are the formula with exactly one satisfying assignment and <span class="math-container">$A_{NO}$</span> are the formula with no satisfying assignment. Then <span class="math-container">$P^A$</span> is contained in <span class="math-container">$\oplus P$</span>. We also have <span class="math-container">$NP\subseteq BPP^A$</span> by Valiant-Vazirani. Both these tools are used in the proof of Toda's theorem.</p>

CC BY-SA 4.0
2020-10-30T21:02:43.450Z
2020-10-30T21:02:43.450Z
Lance Fortnow
<p>Let <span class="math-container">$A=(A_{YES},A_{NO})$</span> be some promise problem (such as xSAT, the Local Hamiltonian problem, etc). Suppose we want to show that a P machine with access to a the oracle A can always have its output predicted by a NEXP machine, i.e. <span class="math-container">$P^A\subseteq$</span> NEXP. We adopt the convention that if P submits a query  which doesn't satisfy the promise of A (that is, <span class="math-container">$x\not\in A_{YES}\cup A_{NO}$</span>), then the oracle for A randomly returns 0 or 1 <span class="math-container">$^*$</span>.
Suppose further that for all <em>valid</em> queries (i.e. those satisfying the promise, <span class="math-container">$x\in A_{YES}\cup A_{NO}$</span>) there exists a single witness which (when run by an EXP machine) allows all queries to the oracle A to be predicted.
Finally, let it is be trivial (i.e. in P) to determine whether a query <span class="math-container">$x$</span> satisfies the promise or not.
Then is it correct to say <span class="math-container">$P^A\subseteq$</span> NEXP?</p>
<p>If the P machine were guaranteed to only make valid queries, then it seems like this is trivial as the NEXP machine is (by assumption) capable of simulating the oracle outcomes and any processing done by the P machine. However, the fact that the P machine can make invalid queries which return 0 or 1 randomly could potentially throw a problem in the simulation.</p>
<p>So far all I've found is Oded Goldreich's notes on promise problems. These don't give a direct answer, but do introduce smart reductions: <a href="http://www.wisdom.weizmann.ac.il/%7Eoded/PSX/prpr-r.pdf" rel="nofollow noreferrer">http://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf</a>
Smart reductions seem to force the P machine to only make valid queries. So in this case it would perhaps be correct to say <span class="math-container">$P_S^A\subseteq$</span>NEXP, where <span class="math-container">$P_S$</span> is a ``smart TM'' which only makes valid queries. But is it correct to state the stronger result that <span class="math-container">$P^A\subseteq$</span>NEXP?</p>
<p><span class="math-container">$^*$</span>As I understand it, this is standard (see the link to Oded Goldreich's notes above).</p>

CC BY-SA 4.0
2020-09-15T05:37:41.507Z
What's $P$?  What does the notation $P^A \subseteq NEXP$ mean for you?  What precisely do you mean by "simulating" queries?  Do you mean there exists an algorithm that produces those queries?  Or also the responses, too?  I think it might be useful to be precise about your language and your understanding of what the notation means, and to write it out carefully in your post.  Goldreich's notes don't say "randomly", they say "arbitrarily". "random" != "arbitrary"
D.W.
CC BY-SA 4.0
2020-09-15T09:57:15.173Z
Have changed to (hopefully!) make clearer. As for the arbitrary!=random distinction, I agree this is true. However, surely one could argue that "arbitrary" includes the possibility of random outputs, which is the worst case scenario here. If the output is arbitrary and known then the question above seems to be trivial...
Hans Schmuber
CC BY-SA 4.0
2020-09-15T10:13:44.107Z
If you can determine in P whether a query satisfies the promise or not, then just don’t ask the oracle queries that do not satisfy the promise, and the problem disappears.
Emil Jeřábek
CC BY-SA 4.0
2020-09-15T10:47:32.793Z
If we're trying to prove P^A\subseteq NEXP, surely we need to prove NEXP can simulate all P machines with oracle access, even those that make queries that don't satisfy the promise? Unless the output of P^A doesn't depend on the outcome of these queries, but I can't understand why that is generally the case (perhaps I'm missing something).
Hans Schmuber
CC BY-SA 4.0
2020-09-15T12:14:22.910Z
Independence on the outcome has to be part of the definition of acceptance, if it is supposed to make any sense. Alternatively, the definition may be that $P^A$ only computes a promise problem, the promise being that it never asks queries that break the original promise. Either way, you should consult the definition.
Emil Jeřábek
<complexity-classes><time-complexity><reductions><promise-problems>
Can a NEXP machine simulate invalid queries to a promise problem oracle?
Hans Schmuber
# Can a NEXP machine simulate invalid queries to a promise problem oracle?

(Asked by: username_0 on 2020-09-14)

Let $A=(A\_{YES},A\_{NO})$ be some promise problem (such as xSAT, the Local Hamiltonian problem, etc). Suppose we want to show that a P machine with access to a the oracle A can always have its output predicted by a NEXP machine, i.e. $P^A\subseteq$ NEXP. We adopt the convention that if P submits a query which doesn't satisfy the promise of A (that is, $x\not\in A\_{YES}\cup A\_{NO}$), then the oracle for A randomly returns 0 or 1 $^\*$.
Suppose further that for all *valid* queries (i.e. those satisfying the promise, $x\in A\_{YES}\cup A\_{NO}$) there exists a single witness which (when run by an EXP machine) allows all queries to the oracle A to be predicted.
Finally, let it is be trivial (i.e. in P) to determine whether a query $x$ satisfies the promise or not.
Then is it correct to say $P^A\subseteq$ NEXP?

If the P machine were guaranteed to only make valid queries, then it seems like this is trivial as the NEXP machine is (by assumption) capable of simulating the oracle outcomes and any processing done by the P machine. However, the fact that the P machine can make invalid queries which return 0 or 1 randomly could potentially throw a problem in the simulation.

So far all I've found is Oded Goldreich's notes on promise problems. These don't give a direct answer, but do introduce smart reductions: [http://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf](http://www.wisdom.weizmann.ac.il/%7Eoded/PSX/prpr-r.pdf)
Smart reductions seem to force the P machine to only make valid queries. So in this case it would perhaps be correct to say $P\_S^A\subseteq$NEXP, where $P\_S$ is a ``smart TM'' which only makes valid queries. But is it correct to state the stronger result that $P^A\subseteq$NEXP?

$^\*$As I understand it, this is standard (see the link to Oded Goldreich's notes above).

**Tags:** complexity-classes, time-complexity, reductions, promise-problems

> **Comments:**
> **username_1**: What's $P$?  What does the notation $P^A \subseteq NEXP$ mean for you?  What precisely do you mean by "simulating" queries?  Do you mean there exists an algorithm that produces those queries?  Or also the responses, too?  I think it might be useful to be precise about your language and your understanding of what the notation means, and to write it out carefully in your post.  Goldreich's notes don't say "randomly", they say "arbitrarily". "random" != "arbitrary"  
> **username_0**: Have changed to (hopefully!) make clearer. As for the arbitrary!=random distinction, I agree this is true. However, surely one could argue that "arbitrary" includes the possibility of random outputs, which is the worst case scenario here. If the output is arbitrary and known then the question above seems to be trivial...  
> **username_2**: If you can determine in P whether a query satisfies the promise or not, then just don’t ask the oracle queries that do not satisfy the promise, and the problem disappears.  
> **username_0**: If we're trying to prove P^A\subseteq NEXP, surely we need to prove NEXP can simulate all P machines with oracle access, even those that make queries that don't satisfy the promise? Unless the output of P^A doesn't depend on the outcome of these queries, but I can't understand why that is generally the case (perhaps I'm missing something).  
> **username_2**: Independence on the outcome has to be part of the definition of acceptance, if it is supposed to make any sense. Alternatively, the definition may be that $P^A$ only computes a promise problem, the promise being that it never asks queries that break the original promise. Either way, you should consult the definition.  

---

## 1 answers

### Answer by username_3 on 2020-10-30. Score: 1

Let's define what P$^A$ means in the promise setting: A language L is in P$^A$ if there is a polytime oracle machine $M$ such that for all sets $B$ such that $B$ contains $A\_{YES}$ and $B\cap A\_{NO}=\emptyset$, $L=L(M^B)$. In other words, the polytime machine can ask queries that are not part of the promise but its output cannot depend on whether those queries are answered yes or no.

For example, consider unique SAT where $A\_{YES}$ are the formula with exactly one satisfying assignment and $A\_{NO}$ are the formula with no satisfying assignment. Then $P^A$ is contained in $\oplus P$. We also have $NP\subseteq BPP^A$ by Valiant-Vazirani. Both these tools are used in the proof of Toda's theorem.


---

