# Assuming NP $\neq$ P, are there NPI languages only P languages reduce to?

let $L_c$ be the class of all languages that have a polynomial reduction to some language L, for example if $L=SAT$ then $SAT_c=NP$.

Assuming know that $NP\neq P$ we know that there exist languages that are not NP-hard and not in P, i.e. those in NPI. My question is there a language L in NPI such that $L_c \setminus \{L\}=P$?

• So what you're looking for is a problem not in $P$ that everything in $P$ reduces to, but nothing outside of $P$ does (except itself)? Some sort of supremum problem for $P$ I guess. – Luke Mathieson May 27 '13 at 6:29
• If we are allowed to use polytime reductions, we can reduce every problem in P to some trivial instance of L. The hard part is finding a language that is weak enough that no other language outside of P reduces to it. – adrianN May 27 '13 at 8:31

I don't think such a language $L$ can exist, because it suffices to slightly modify it to get a language $L'\in L_c$ and not in $P$. For instance let $u$ be a word of minimal length which is not in $L$, and take $L'=L\cup\{u\}$. It is clear that $L'$ polynomially reduces to $L$: check if the input word is $u$, and if it's not use your oracle for $L$. Since $u$ is of constant size, this algorithm runs in polynomial time. So $L'\in L_c$. But you also have the inverse reduction: $L$ polynomially reduces to $L'$. This implies that $L'\notin P$, because otherwise $L$ would also be in $P$.
• Is there other conditions that will make $L_c=P$ and still $L\notin P$ – Fayez Abdlrazaq Deab May 28 '13 at 12:00
• If $L_c=P$ then you will always have $L\in P$, because $L_c$ contains a lot of languages that behave exactly like $L$, like re-encodings of $L$ (for instance double each letter), or the one in my answer. – Denis May 28 '13 at 14:19