MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?

Equally interesting would be to learn about such problems with a non-trivial proof of polytime complexity. Is there anything well-known besides the graph factoring problem?

share|cite|improve this question
What do you mean by "related to the notion of Cartesian product"? – Qiaochu Yuan Oct 5 '12 at 18:12
Either the operation of cartesian product on some structures is explicitly present in the formulation of the problem, or the complexity proof mentions this operation. – Martin Oct 6 '12 at 8:17
Are you o.k. with cartesian products of posets? Perhaps the problem of deciding whether a finite poset is a nontrivial cartesian product in NP-hard. – Richard Stanley Oct 7 '12 at 0:32
That seems like an incredibly broad requirement. Any time you work with a function that takes at least two inputs, you could say you're working with Cartesian products. What do you actually want to know? – Qiaochu Yuan Oct 7 '12 at 5:13
@Qiaochu Yuan: This is important to realize, thanks for this remark. I'd like to learn about problems like the one mentioned by Richard (see above). – Martin Oct 8 '12 at 10:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.