| Input: | H-description of a polyhedron P Ì Qd, c Î Qd, C Î Q |
|---|---|
| Output: | "Yes" if there is a vertex v of P with cTv = C; "No" otherwise |
| Status (general): | Strongly NP-complete |
|---|---|
| Status (fixed dim.): | Polynomial time |
| Proved to be NP-complete by Chandrasekaran, Kabadi, and Murty [11] and strongly NP-complete by Fukuda, Liebling, and Margot [22]. The problem remains strongly NP-complete even if the input is restricted to polytopes [22]. |
| Related problems: | 25, 26 |
|---|