|Input:||Vertex-facet incidence matrices AP and AQ of polytopes P and Q, respectively|
|Output:||"Yes" if AP can be transformed into AQ by row and column permutations, "No" otherwise|
|Status (general):||Graph isomorphism complete|
|Status (fixed dim.):||Polynomial time|
The problem remains graph isomorphism complete even if
V- and H-descriptions of P and Q are
part of the input data .
In constant dimension the problem can be solved in polynomial time by a reduction  to the graph isomorphism problem for graphs of bounded degree, for which a polynomial time algorithm is known (Luks ).
Problem 22 can polynomially be reduced to this problem. For polytopes of bounded dimension both problems are polynomial time equivalent.
|Related problems:||22, 21|