Is there an NP complete language having no polytime decidable superset (apart from the set of all strings)?
-
$\begingroup$ What about the set of all strings, excluding "foo"? $\endgroup$– user253751Nov 30, 2015 at 20:16
-
$\begingroup$ @immibis see edit to question Pl. $\endgroup$– ARiDec 5, 2015 at 10:27
-
$\begingroup$ Rolled back edit which invalidated answers. $\endgroup$– David RicherbyDec 5, 2015 at 10:58
2 Answers
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.
-
$\begingroup$ 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). $\endgroup$– ARiDec 5, 2015 at 10:33
-
1$\begingroup$ Please do not change questions in ways that invalidate existing answers. If you want to ask a new question, ask a new question. $\endgroup$ Dec 5, 2015 at 10:57
-
1$\begingroup$ @DavodRicjerby I agree.I have it here cs.stackexchange.com/q/50355/42961 $\endgroup$– ARiDec 5, 2015 at 17:10
-
$\begingroup$ I choose this answer over the other as I like the construction. Thanks $\endgroup$– ARiDec 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^*$.
-
$\begingroup$ +1 This is a simpler (and, therefore, better) version of the idea I was presenting. $\endgroup$ Nov 30, 2015 at 20:59