Could it be that three languages $A, B, C$ such that $A \subset B \subset C$, and $B \in P$, but $A$ and $C$ are $NP$-complete?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
Let $L$ be any NP-complete language over $\Sigma = \{0,1\}$, and take \begin{align} A &= \{ 0x : x \in L \} \\ B &= 0\Sigma^* \\ C &= 0\Sigma^* \cup \{ 1x : x \in L \} \end{align}
answered Dec 2 '20 at 12:52
-
$\begingroup$ Should $L$ be unary over $\Sigma = \{0\}$? $\endgroup$ – Luke Mathieson Dec 2 '20 at 12:54
-
-
-
$\begingroup$ We don't expect there to exist NP-complete sparse languages. $\endgroup$ – Yuval Filmus Dec 2 '20 at 12:57
-
$\begingroup$ Yeah, I was heading off in that direction, but then thought of the other problem, and now it all works perfectly. :) $\endgroup$ – Luke Mathieson Dec 2 '20 at 12:57
