Interval Dimension
The interval dimension of a partial order can be defined as the minimal number of interval order extensions realizing this order, in a similar way to the definition of the order dimension which uses linear extensions. The interval dimension of an order is always less than its order dimension, but interval orders with high dimensions are known to exist. While the problem of determining the order dimension of general partial orders is known to be NP-complete, the complexity of determining the order dimension of an interval order is unknown.
Read more about this topic: Interval Order
Famous quotes containing the words interval and/or dimension:
“The yearning for an afterlife is the opposite of selfish: it is love and praise for the world that we are privileged, in this complex interval of light, to witness and experience.”
—John Updike (b. 1932)
“Authority is the spiritual dimension of power because it depends upon faith in a system of meaning that decrees the necessity of the hierarchical order and so provides for the unity of imperative control.”
—Shoshana Zuboff (b. 1951)