1
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\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, 2020 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$
    – Hans Schmuber
    Sep 15, 2020 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, 2020 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$
    – Hans Schmuber
    Sep 15, 2020 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, 2020 at 12:14

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.