I've been back and forth about this one. I have the following theoretical homework problem, which describes the SET-INTERSECTION problem. In my homework, it's presented as being NP-complete.

the so called set intersection problem

Does this problem have a more common name in general Computer Science nomenclature? I'm trying to wrap my head around the definition itself -- and I can't find any resources that refer to the "set intersection problem" with similar parameters to this except in this pdf. It seems similar to the unit intersection problem described in a math stackexchange post. I also (naively?) think that it might be the set cover problem.

My actual intent is to understand what the problem describes -- so I'm looking for alternate names and resources that lead in the right direction. I'm not asking for any specific help in proving properties of it -- just understanding what it describes.

  • $\begingroup$ There are a lot of similarities to "hitting set", which itself is set cover in disguise. $\endgroup$
    – mhum
    Apr 24 '18 at 19:03

To the best of my knowledge, there is no other name for this.


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.