World's most popular travel blog for travel bloggers.

On intersection of classes

, , No Comments
Problem Detail: 

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?

Asked By : Turbo
Answered By : David Richerby

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?"

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback