4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ What about the set of all strings, excluding "foo"? $\endgroup$ – user253751 Nov 30 '15 at 20:16
  • $\begingroup$ @immibis see edit to question Pl. $\endgroup$ – ARi Dec 5 '15 at 10:27
  • $\begingroup$ Rolled back edit which invalidated answers. $\endgroup$ – David Richerby Dec 5 '15 at 10:58
6
$\begingroup$

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.

$\endgroup$
4
  • $\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$ – ARi Dec 5 '15 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$ – David Richerby Dec 5 '15 at 10:57
  • 1
    $\begingroup$ @DavodRicjerby I agree.I have it here cs.stackexchange.com/q/50355/42961 $\endgroup$ – ARi Dec 5 '15 at 17:10
  • $\begingroup$ I choose this answer over the other as I like the construction. Thanks $\endgroup$ – ARi Dec 9 '15 at 16:44
8
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ +1 This is a simpler (and, therefore, better) version of the idea I was presenting. $\endgroup$ – David Richerby Nov 30 '15 at 20:59

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.