Consider classes $\mathcal C_1$ and $\mathcal C_2$ of problems both of which are $\mathsf{NP}$-complete. Does it mean $\mathcal C_1\cap\mathcal C_2$ of problems is $\mathsf{NP}$-complete?


closed as unclear what you're asking by D.W. Apr 29 '16 at 3:11

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ It's not clear what you mean by "class of problems...[is] NP-complete", so the problem doesn't seem well-specified at present. The definition of NP-completeness applies to problems, not classes of problems. Please edit the question to clarify what you are asking. Also, as always, you should show your thoughts and what thinking you've already done. $\endgroup$ – D.W. Apr 29 '16 at 3:10
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – D.W. Apr 29 '16 at 3:11

I'm not sure what you mean by a class of problems being NP-complete ndash; perhaps that every problem in the class is NP-complete?

In any case, it sounds like it's possible that $\mathcal{C}_1\cap\mathcal{C}_2 = \emptyset$, in which case the answer seems to be "no". (Well, except that every problem in $\emptyset$ is NP-complete, in which case the answer would be "yes" but for vacuous reasons.)

In general, whenever you're asked about closure properties of families of languages, a good first question to ask yourself is, "Can I make the answer trivial by engineering the intersection/union/whatever to be either the emptyset or every possible thing?"

  • $\begingroup$ I assumed they have non-trivial intersection apriori. Another reason I asked was many NP complete problems can be morphed to one another. I wanted to see if there is even an easy way to define intersection in that scenario. It is a badly framer post but not unsure how to make it better. $\endgroup$ – T.... Apr 29 '16 at 1:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.