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

  • $\begingroup$ 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" $\endgroup$ – D.W. Sep 15 at 5:37
  • $\begingroup$ 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... $\endgroup$ – user138901 Sep 15 at 9:57
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Sep 15 at 10:13
  • $\begingroup$ 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). $\endgroup$ – user138901 Sep 15 at 10:47
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Sep 15 at 12:14

Your Answer

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

Browse other questions tagged or ask your own question.