Go up to 4 Isomorphism
Go forward to 21 Combinatorial Equivalence of V-Polytopes
|
Go up to 4 Isomorphism Go forward to 21 Combinatorial Equivalence of V-Polytopes |
XHTML 1.0 |
| Input: | Two polytopes P and Q given in V-description |
|---|---|
| Output: | "Yes" if P is affinely equivalent to Q, "No" otherwise |
| Status (general): | Graph isomorphism hard |
|---|---|
| Status (fixed dim.): | Polynomial time |
|
The graph isomorphism problem can polynomially be reduced to the
problem of checking the affine equivalence of two
polytopes [34]. The problem remains graph isomorphism
hard if H-descriptions are additionally provided as
input data and/or if one restricts the input to simple or simplicial
polytopes.
For polytopes of bounded dimension the problem can be solved in polynomial time by mere enumeration of affine bases among the vertex sets. |
| Related problems: | 21 |
|---|
|
|
Why are some symbols not displayed correctly? |