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:
“[I have] been in love with one princess or another almost all my life, and I hope I shall go on so, till I die, being firmly persuaded, that if ever I do a mean action, it must be in some interval betwixt one passion and another.”
—Laurence Sterne (1713–1768)
“By intervening in the Vietnamese struggle the United States was attempting to fit its global strategies into a world of hillocks and hamlets, to reduce its majestic concerns for the containment of communism and the security of the Free World to a dimension where governments rose and fell as a result of arguments between two colonels’ wives.”
—Frances Fitzgerald (b. 1940)