<p>Depends on your definition of NPI. If A is incomplete for Turing reductions, the answer is yes since SAT is not in $P^A$.</p>

<p>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 <a href="http://people.cs.uchicago.edu/~fortnow/papers/newiso.pdf">this paper</a>).</p>

CC BY-SA 3.0
2014-05-29T18:04:19.827Z
Do you mean Theorem 1.9?
Geoffrey Irving
CC BY-SA 3.0
2014-05-29T20:18:45.150Z
You are right. Fixed.
Lance Fortnow
CC BY-SA 3.0
2014-05-29T17:22:18.030Z
2014-05-29T20:18:06.323Z
2014-05-29T20:18:06.323Z
Lance Fortnow
<p>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?</p>

CC BY-SA 3.0
2014-05-29T14:31:52.343Z
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!]
Bruno
<cc.complexity-theory><complexity-classes><np-intermediate>
Is $P^{NPI}$ different from $P^{NP}$?
GMB
# Is $P^{NPI}$ different from $P^{NP}$?

(Asked by: username_0 on 2014-05-29)

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?

**Tags:** cc.complexity-theory, complexity-classes, np-intermediate
> **Comments:**
> **username_1**: 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!]  

---

## 1 answers

### Answer by username_2 on 2014-05-29. Score: 16 | Accepted answer

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](http://people.cs.uchicago.edu/~fortnow/papers/newiso.pdf)).

> **Comments:**
> **username_3**: Do you mean Theorem 1.9?  
> **username_2**: You are right. Fixed.  

---

