2
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ Should $L$ be unary over $\Sigma = \{0\}$? $\endgroup$ – Luke Mathieson Dec 2 '20 at 12:54
  • $\begingroup$ How do you get $A \subset B$? $\endgroup$ – Luke Mathieson Dec 2 '20 at 12:55
  • $\begingroup$ Thanks for the correction. $\endgroup$ – Yuval Filmus Dec 2 '20 at 12:56
  • $\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

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.