3
$\begingroup$

Baker, Gill, and Solovay has shown in their famous paper, that there are oracles $A$ and $B$ with $P^A = NP^A$ and $P^B \not= NP^B$. So, one can't solve the $P$ vs. $NP$ Problem with methods like diagonalization alone.

To find the oracle $A$ is easy. But the construction of oracle $B$ is very complicated in the paper. Can we use a simpler oracle?

Does anyone tried a $P$-complete oracle? Is $P^P \not= NP^P$? Would this result be a solution of the $P$ vs. $NP$ Problem?

$\endgroup$

3 Answers 3

7
$\begingroup$

If $B$ is chosen at random, then $\mathsf{P}^B \neq \mathsf{NP}^B$ almost surely. See for example lecture notes of Luca Trevisan, Schöning and Pruim's gem, or the original paper of Bennett and Gill.

$\endgroup$
0
$\begingroup$

There is an easy way to find such an oracle that $P^B\not=NP^B$. The set $ S = \{\langle M, 1^n, 1^t\rangle \mid \exists x\in\{0,1\}^n \text{ with TM }M\text{ accepts }x\text{ within }t\text{ steps}\}$ in $NP$-complete. We use the oracle $B = \langle M, x, 1^t\rangle \mid M \text{ accepts }x \text{ within }t\text{ steps}\}$. The oracle $B$ is $P$-complete (via logspace reduction). So, $S^B = NP^B =NP^P$.

If $t$ is very big ($t\to\infty$), then for a fixed $M$ and $x$ there is a $t$ with $\forall x\in\{0,1\}^n : \langle M, 1^n, 1^t\rangle \in S \iff x\in L(M)$.

Due to Rice's theorem the set $\{x\in\{0,1\}^n\mid x\in L(M)\}$ is undecidable. So, for large $t$ one have to call the oracle $B$ for each $x\in\{0,1\}^n$ in the worst case on a determinstic OTM. This means $2^n$ accesses to the oracle $B$. So, $P^B\not=NP^B$. And $P^P\not=NP^P$, since $B$ is $P$-complete.

$\endgroup$
0
$\begingroup$

You've not specified which notion of P-completeness you mean, but no matter which one, note that every $P$-complete set is in particular in $P$. The question is thus essentially "given a poly-time oracle $A$, what are $P^A$ and $NP^A$?"

The answer is that these are $P$ and $NP$ respectively. For any poly-time computable set $A$ there exists a Turing machine $M_A$ that computes it. Any poly-time oracle Turing machine $M$ will, on input $x$, performs at most $k$ queries to the oracle, say $y_1, \ldots, y_k$. As $M$ is poly-time, both $k$ and each $|y_i|$ are polynomial in $|x|$. It follows that the Turing machine $M'$ that simulates $M$ but uses $M_A$ to resolve the oracle queries will take at most polynomial extra time, and thus is itself a poly-time computation. Hence every $P^A$-computable set is in fact $P$-computable.

A similar argument works for the non-deterministic case; every possible computation path will take at most polynomial extra time, so the computation as a whole will take polynomial extra time as well.

$\endgroup$

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.