Can a NEXP machine simulate invalid queries to a promise problem oracle?

Question

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

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