Skip to main content

New answers tagged

5 votes
Accepted

Showing the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard

Let's flip this around using the fact that $L$ is $\text{NP}$-hard iff $\overline{L}$ is $\text{coNP}$-hard. You want to show that $$\text{3-Col} \cup \overline{\text{4-Col}} \text{ is NP-hard}.$$ To ...
Benjamin Kuykendall's user avatar
6 votes
Accepted

If coNP ⊆ NP, does that mean coNP = NP?

Yes. Assume co-NP ⊆ NP. Take any NP problem. Its complement is co-NP, therefore NP by co-NP ⊆ NP, so the problem itself is co-NP, QED.
Jean Abou Samra's user avatar

Top 50 recent answers are included