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)
“God cannot be seen: he is too bright for sight; nor grasped: he is too pure for touch; nor measured: for he is beyond all sense, infinite, measureless, his dimension known to himself alone.”
—Marcus Minucius Felix (2nd or 3rd cen. A.D.)