NP complete language having no Polytime decidable superset

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

• What about the set of all strings, excluding "foo"? Nov 30, 2015 at 20:16
• @immibis see edit to question Pl.
– ARi
Dec 5, 2015 at 10:27
• Rolled back edit which invalidated answers. Dec 5, 2015 at 10:58

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.

• Pl see my edit above. Your polytime superset Ln is short of the set of all strings by finitely many(determined by the choice of n).
– ARi
Dec 5, 2015 at 10:33
• Please do not change questions in ways that invalidate existing answers. If you want to ask a new question, ask a new question. Dec 5, 2015 at 10:57
• @DavodRicjerby I agree.I have it here cs.stackexchange.com/q/50355/42961
– ARi
Dec 5, 2015 at 17:10
• I choose this answer over the other as I like the construction. Thanks
– ARi
Dec 9, 2015 at 16:44

A slightly simpler proof is to note that $\Sigma^* \setminus \{w\}$ is polynomial-time decidable and a superset of any language $L$ where $w\notin L$. Formally:

Suppose $P\not = NP$ and let $L$ be some $NP$-complete language. Then there exist at least $2$ strings $v\not = w$ so that $v\not \in L, w\not \in L$ or $L$ would not be $NP$-complete (since $L$ would either be $\Sigma^*$ or $\Sigma^*\setminus L$ would be a singleton). Then $\Sigma^{*}\setminus \{w\}$ is polynomially decidable and a superset of $L$ (since $v\in \Sigma^{*}\setminus \{w\}$).

If $P=NP$ then every language that is not $\emptyset$ or $\Sigma^*$ is $NP$-hard, so in particular $\Sigma^* \setminus \{x\}$ is $NP$-complete (where $x$ is any string in $\Sigma^*$). However, $\Sigma^* \setminus \{x\}$ has no (proper) superset that is not $\Sigma^*$. So if $P=NP$, there is a a language having no superset $\in P$ that is not $\Sigma^*$.

• +1 This is a simpler (and, therefore, better) version of the idea I was presenting. Nov 30, 2015 at 20:59