Can we prove that for every language $L\in\mathsf{NP}$ that is not $\mathsf{NP}$-hard (this assumes $\mathsf P \ne \mathsf{NP}$), $\mathsf{P}^L \ne \mathsf{P}^{\text{SAT}}$? Alternately, can this be proven under any reasonable assumptions?
12
$\begingroup$
$\endgroup$
-
$\begingroup$ I think this question has a silly answer: Let $L\in\mathsf P\subseteq\mathsf{NP}$, then certainly $\mathsf P^L\neq \mathsf P^{\text{SAT}}$ once you assume that $\mathsf P\neq\mathsf{NP}$. So you may want, still assuming $\mathsf P\neq\mathsf{NP}$, $L$ to be in $\mathsf{NP}\setminus\mathsf P$ and not $\mathsf{NP}$-hard. [Edit: Oh, I read your comment below, so your question seems to be: "Is that true that for all such $L$, the inequality occurs?", rather than "Does there exist such an $L$?" => I edit your question!] $\endgroup$ – Bruno May 29 '14 at 14:31
16
$\begingroup$
$\endgroup$
Depends on your definition of NPI. If A is incomplete for Turing reductions, the answer is yes since SAT is not in $P^A$.
If A is just many-one incomplete then we don't know how to prove it. We have a relativized world with there is a set A in NP such that A is not NP-complete via many-one reductions but SAT can be computed by a single query to A. (Theorem 1.9 in this paper).
