backup forward

Go backward to 20 Affine Equivalence of V-Polytopes
Go up to 4 Isomorphism
Go forward to 22 Polytope Isomorphism
XHTML 1.0

21 Combinatorial Equivalence of V-Polytopes

Input: Two polytopes P and Q given in V-description
Output: "Yes" if P is combinatorially equivalent to Q, "No" otherwise
Status (general): coNP-hard
Status (fixed dim.): Polynomial time
Swart [62] describes a reduction of the subset-sum problem to the negation of the problem.

For polytopes of bounded dimension the problem can be solved in polynomial time (see Problems 2 and 23).


backup forward Why are some symbols not displayed correctly?