The Complexity of the Partial Order Dimension Problem
Mihalis Yannakakis · SIAM Journal on Algebraic and Discrete Methods · 1982
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 1 or 2. We prove that it is NP-complete to determine if a partial order has dimension 3. As a consequence, several other related dimension-type problems are shown to be NP-complete.