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

Improve this question
$\endgroup$
2
  • $\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, 2013 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, 2013 at 8:31

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is there other conditions that will make $L_c=P$ and still $L\notin P$ $\endgroup$
    – Fayez Abdlrazaq Deab
    May 28, 2013 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, 2013 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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