We define the mechanical complexity $C(P)$ of a convex polyhedron $P,$ interpreted as a homogeneous solid, as the difference between the total number of its faces, edges and vertices and the number of its static equilibria, and the mechanical complexity $C(S,U)$ of primary equilibrium classes $(S,U)^E$ with $S$ stable and $U$ unstable equilibria as the infimum of the mechanical complexity of all polyhedra in that class. We prove that the mechanical complexity of a class $(S,U)^E$ with $S, U > 1$ is the minimum of $2(f+v-S-U)$ over all polyhedral pairs $(f,v )$, where a pair of integers is called a polyhedral pair if there is a convex polyhedron with $f$ faces and $v$ vertices. In particular, we prove that the mechanical complexity of a class $(S,U)^E$ is zero if, and only if there is a convex polyhedron with $S$ faces and $U$ vertices. We also discuss the mechanical complexity of the monostatic classes $(1,U)^E$ and $(S,1)^E$, and offer a complexity-dependent prize for the complexity of the Gömböc-class $(1,1)^E$.