Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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
1  
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

 
discard

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

Browse other questions tagged or ask your own question.