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

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?

-
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
show 1 more comment