Abstrakt
The dimension of a partial order P is the minimum number of linear orders whose intersection is P. There are efficient algorithms to test if a partial order has dimension at most 2.
In 1982 Yannakakis [SIAM J.Algebraic Discrete Methods, 3 (1982), pp. 351-358] showed that for k >= 3 to test if a partial order has dimension = 4 to test if a partial order of height 2 has dimension <= k is NP-complete. The complexity of deciding whether an order of height 2 has dimension 3 was left open.
This question became one of the best known open problems in dimension theory for partial orders. We show that the problem is NP-complete.
Technically, we show that the decision problem (3DH2) for dimension is equivalent to deciding for the existence of bipartite triangle containment representations (BTCon). This problem then allows a reduction from a class of planar satis fi ability problems (P-3-CON-3-SAT(4)) which is known to be NP-hard.