|Input:||Polytope P in H-description|
|Output:||Number of vertices of P|
|Status (fixed dim.):||Polynomial time|
Dyer  and Linial  independently proved
that NUMBER OF VERTICES is #P-complete. It follows
that the problem of computing the f-vector of P is #P-hard.
Furthermore, Dyer  proved that the decision version
("Given a number k, does P have at least k vertices?") is
strongly NP-hard and remains NP-hard when restricted to simple
polytopes. It is unknown whether the decision problem is in NP.
If the dimension is fixed, one can enumerate all vertices in polynomial time (see Problem 1).
|Related problems:||1, 15|