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!
1
-
$\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$– greybeardCommented May 26, 2020 at 6:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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?
-
-
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. ♦Commented May 24, 2020 at 19:18
-
-
$\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$– GodderCommented May 24, 2020 at 20:13