Order Dimension - Computational Complexity

Computational Complexity

It is possible to determine in polynomial time whether a given finite partially ordered set has order dimension at most two, for instance, by testing whether the comparability graph of the partial order is a permutation graph. However, for any k ≥ 3, it is NP-complete to test whether the order dimension is at most k (Yannakakis 1982).

Read more about this topic:  Order Dimension

Famous quotes containing the word complexity:

    It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.
    Elaine Heffner (20th century)