1
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ What do you mean by "related to the notion of Cartesian product"? $\endgroup$
    – Qiaochu Yuan
    Commented Oct 5, 2012 at 18:12
  • $\begingroup$ 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. $\endgroup$
    – Martin
    Commented Oct 6, 2012 at 8:17
  • $\begingroup$ 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. $\endgroup$
    – Richard Stanley
    Commented Oct 7, 2012 at 0:32
  • 1
    $\begingroup$ 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? $\endgroup$
    – Qiaochu Yuan
    Commented Oct 7, 2012 at 5:13
  • $\begingroup$ @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). $\endgroup$
    – Martin
    Commented Oct 8, 2012 at 10:57

0

Reset to default

You must log in to answer this question.