The Hardness of Approximating Poset Dimension

The dimension of a partially ordered set (poset) is the minimum integer k such that the partial order can be expressed as the intersection of k total orders. We prove that there exists no polynomial-time algorithm to approximate the dimension of a poset on N elements with a factor of O ( N 0.5 − ϵ ) for any ϵ > 0 , unless NP = ZPP . The same hardness of approximation holds for the fractional version of poset dimension, which was not even known to be NP-hard.