patternMinor
NP complete language having no Polytime decidable superset
Viewed 0 times
polytimehavinglanguagedecidablecompletesuperset
Problem
Is there an NP complete language having no polytime decidable superset (apart from the set of all strings)?
Solution
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^$.
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^$.
Context
StackExchange Computer Science Q#50123, answer score: 8
Revisions (0)
No revisions yet.