3
$\begingroup$

I know that the general consensus among CS researchers is that non-relativizing techniques will be needed to separate P and NP. However, if there is an oracle language $A \in \textbf{P}$ such that ${\textbf{P}}^A \neq {\textbf{NP}}^A$ would that necessarily imply ${\textbf{P}} \neq {\textbf{NP}}$? I read somewhere that it would be enough, but I'm not sure.

On the one hand, since any NDTM can be supplemented with a polynomial-time deterministic subroutine for $A$, having oracle access to it should not give an NDTM any more "power".

On the other hand though, aren't oracle TM's able to make queries about strings of any length in the oracle language? In that case, we could not jump to the conclusion that P does not equal NP, because according to my understanding, polynomial-time Turing machines (whether deterministic or non-deterministic) cannot be "influenced" by strings of length exponential in the length of the input string.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Non-relativizing techniques are needed precisely because we can find oracles $A, B$ such that $P^A \ne NP^A$ and $P^B = NP^B$. $\endgroup$
    – Nicholas Mancuso
    Commented Dec 5, 2014 at 18:48
  • $\begingroup$ @Nicholas I realize that such oracles exist relativizing the question both ways. However, if we know more about the oracle languages themselves, I thought we might be able to draw a definite conclusion. For example if P = NP by an oracle in P, wouldn't that imply that P equals NP? I just know of PSPACE and EXPTIME oracles that achieve this result. While we still don't know if P is properly contained in PSPACE we do know that is certainly properly contained in EXPTIME, so we cannot draw any conclusions from these oracles. I was wondering about the other direction as well. $\endgroup$
    – Ari
    Commented Dec 5, 2014 at 20:32
  • $\begingroup$ have pondered this myself & asked this related cstheory question to try to sort it out, what class is the B language in the BGS75 result? the BGS75 result is mainly what led to the apparent "consensus" you refer to, take a look. essentially apparently if a relativization result could be found with sufficient constraints on the oracle, it could prove either P=NP or P≠NP. deep stuff, maybe all worth some further discussion? $\endgroup$
    – vzn
    Commented Jun 23, 2015 at 1:45

1 Answer 1

Reset to default
7
$\begingroup$

For an oracle $A\in {\sf P}$ you have ${\sf P}^A={\sf P}$ (since you can encode all requests to the oracle as a submodule of the TM). By the same argument you als have that ${\sf NP}^A={\sf NP}$.

Thus in this case ${\sf NP}^A\neq{\sf P}^A$ would imply ${\sf NP}\neq{\sf P}$.

You basically said this already in your question. Note that we cannot query "exponentially long" strings to the oracle, since we need to write the string on the oracle tape first, and this would clearly take too long. Maybe this caused your confusion?

Improve this answer
$\endgroup$
4
  • $\begingroup$ I guess I am just misunderstanding the definition of oracle Turing machines since the textbooks I have read just mention the membership status of a string in the oracle is determined in one computation step. $\endgroup$
    – Ari
    Commented Dec 6, 2014 at 23:15
  • $\begingroup$ @Ari: Right it takes one step to get an answer from the oracle, while the tape is erased. However, the query has to be printed on the tape! $\endgroup$
    – A.Schulz
    Commented Dec 7, 2014 at 6:41
  • $\begingroup$ Then how is $P^A$ interpreted for an EXPTIME-complete oracle $A$? Doesn't it query exponentially large strings? $\endgroup$
    – Ari
    Commented Dec 7, 2014 at 15:15
  • 1
    $\begingroup$ ... $P^A$ is interpreted as the set of languages such that an oracle for $A$ allows them to be decided in polynomial time. $\:$ Note that EXPTIME$^A$ can query exponentially long "strings to the oracle, since" it can take the amount of time needed "to write the string on the oracle tape first". $\;\;\;\;$ $\endgroup$
    – user12859
    Commented Dec 8, 2014 at 4:47

Your Answer

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

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