1
$\begingroup$

I'm pretty new to complexity theory and it seems like I stuck with this problem. We should find language $B$ such that it accepts any words rejected by $A$ but in that case, it seems that $B$ is a complement of $A$ and therefore $B$ belongs to $coNPC$. What is my mistake? Thank you!

$\endgroup$
  • $\begingroup$ Welcome to COMPUTERSCIENCE @SE. (Please make the body of your questions self contained. In particular, re-state essentials from the title.) I remember accept and reject of automata - languages contain words, don't, or even show no way of deciding that. What do you know about $A \cap B$? $\endgroup$ – greybeard May 26 at 6:33
1
$\begingroup$

Hint: let $A$ be a NP-complete language and $B=\Sigma^*$. Then $A \cup B = \Sigma^*$. Is $B$ the complement of $A$? Does it belong to coNPC?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $B$ is not NP-complete here. $\endgroup$ – orlp May 24 at 19:16
  • 1
    $\begingroup$ @orlp I'm aware of that. I'm making a point about the key mistake the poster has made, while still allowing them to solve their own exercise. $\endgroup$ – D.W. May 24 at 19:18
  • $\begingroup$ Ah I see, my bad. $\endgroup$ – orlp May 24 at 19:24
  • $\begingroup$ Oh, it means that $B$ is not necessarily a complement of $A$ and therefore intersection $A \cap B \neq \emptyset $ .I got it, thanks a lot. $\endgroup$ – Godder May 24 at 20:13

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.