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(N0.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.