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?

  • $\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

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).

  • $\begingroup$ Do you mean Theorem 1.9? $\endgroup$ – Geoffrey Irving May 29 '14 at 18:04
  • $\begingroup$ You are right. Fixed. $\endgroup$ – Lance Fortnow May 29 '14 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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