AProPo -- 7 Number of Vertices

Go backward to 6 Degeneracy Testing
Go up to 2 Coordinate Descriptions
Go forward to 8 Feasible Basis Extension

7 Number of Vertices

Input:	Polytope P in H-description
Output:	Number of vertices of P

Status (general):	#P-complete
Status (fixed dim.):	Polynomial time

Dyer [14] and Linial [40] 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 [14] 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).