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$ Nov 30, 2015 at 20:16
  • $\begingroup$ @immibis see edit to question Pl. $\endgroup$
    – ARi
    Dec 5, 2015 at 10:27
  • $\begingroup$ Rolled back edit which invalidated answers. $\endgroup$ Dec 5, 2015 at 10:58

2 Answers 2

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, 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$
    – ARi
    Dec 5, 2015 at 17:10
  • $\begingroup$ I choose this answer over the other as I like the construction. Thanks $\endgroup$
    – ARi
    Dec 9, 2015 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$ Nov 30, 2015 at 20:59

Your Answer

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

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