Go backward to 26 Optimal Vertex Go up to 5 Optimization Go forward to 28 AOF Cube Programming |
XHTML 1.0 |
Input: | H-description of a polyhedron P ⊂ Q^{d}, c ∈ Q^{d}, C ∈ Q |
---|---|
Output: | "Yes" if there is a vertex v of P with c^{T}v = 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 |
---|
Why are some symbols not displayed correctly? |