4
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Luke Mathieson May 27 '13 at 6:29
  • $\begingroup$ 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. $\endgroup$ – adrianN May 27 '13 at 8:31
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is there other conditions that will make $L_c=P$ and still $L\notin P$ $\endgroup$ – Fayez Abdlrazaq Deab May 28 '13 at 12:00
  • $\begingroup$ 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. $\endgroup$ – Denis May 28 '13 at 14:19

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.