principleMinor
Can oracle arguments separate P and NP?
Viewed 0 times
canargumentsseparateandoracle
Problem
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.
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.
Solution
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?
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?
Context
StackExchange Computer Science Q#33890, answer score: 7
Revisions (0)
No revisions yet.