  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 showed that for $k\geq 3$
to test if a partial order has dimension $\leq k$ is NP-complete. The height of
a partial order $P$ is the maximum size of a chain in $P$. Yannakakis also
showed that for $k\geq 4$ to test if a partial order of height $2$ has
dimension $\leq 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 satisfiability problems (P-3-CON-3-SAT(4)) which is known to be NP-hard.
