Go backward to 6 Degeneracy Testing
Go up to 2 Coordinate Descriptions
Go forward to 8 Feasible Basis Extension
|
Go backward to 6 Degeneracy Testing Go up to 2 Coordinate Descriptions Go forward to 8 Feasible Basis Extension |
XHTML 1.0 |
| 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). |
| Related problems: | 1, 15 |
|---|
|
|
Why are some symbols not displayed correctly? |