[Solved]: NP complete language having no Polytime decidable superset

Problem Detail: 

Is there an NP complete language having no polytime decidable superset (apart from the set of all strings)?

Asked By : ARi

Answered By : David Richerby

No, assuming P$\,\neq\,$NP. Let $L$ be any NP-complete language over alphabet $\Sigma$ and let $N = \{n\in\mathbb{N}\mid L\cap \Sigma^n\neq \Sigma^n\}$, i.e., $N$ is the set of lengths such that at least one word of length $n$ is not in $L$.

Note that $N$ must be infinite. If not, it has some maximum element $m$ and $L = \big(L\cap \Sigma^{\leq m}\big) \cup \Sigma^{>m}$, which is a regular language, since $L\cap\Sigma^{\leq m}$ is finite. So, in particular, $L$ is in P, contradicting the assumption that it is NP-complete (under the assumption that P$\,\neq\,$NP).

But now pick any $n\in N$ and let $L_n = \big(L\cap \Sigma^{\leq n}\big)\cup\Sigma^{>n}$. $L_n$ is a strict superset of $L$ (because, for any $n<n'\in N$, $L_n$ contains all strings of length $n'$ but $L$ doesn't) and $L_n\in\,$P by the same argument as above.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50123