Skip to main content
deleted 48 characters in body
Source Link

The fact that the underlying polytope $Ax \le b$ is the same for $P_1$ and $P_2$ does not matter, unless we know something specific about $A$ and $b$. This is because a general polytope is an affine projection of a simplex (see, for instance, Ziegler's "Lectures for Polytopes", Theorem 2.15). Thus, if $A$ and $b$ encode a simplex, your question is equivalent to asking how hard general polytope isomorphism is. A quick search reveals the following paper by Kaibel and Schwartz On the Complexity of Polytope Isomorphism ProblemsOn the Complexity of Polytope Isomorphism Problems, where they show that it is Graph Isomorphism hard.

The fact that the underlying polytope $Ax \le b$ is the same for $P_1$ and $P_2$ does not matter, unless we know something specific about $A$ and $b$. This is because a general polytope is an affine projection of a simplex (see, for instance, Ziegler's "Lectures for Polytopes", Theorem 2.15). Thus, if $A$ and $b$ encode a simplex, your question is equivalent to asking how hard general polytope isomorphism is. A quick search reveals the following paper by Kaibel and Schwartz On the Complexity of Polytope Isomorphism Problems, where they show that it is Graph Isomorphism hard.

The fact that the underlying polytope $Ax \le b$ is the same for $P_1$ and $P_2$ does not matter, unless we know something specific about $A$ and $b$. This is because a general polytope is an affine projection of a simplex (see, for instance, Ziegler's "Lectures for Polytopes", Theorem 2.15). Thus, if $A$ and $b$ encode a simplex, your question is equivalent to asking how hard general polytope isomorphism is. A quick search reveals the following paper by Kaibel and Schwartz On the Complexity of Polytope Isomorphism Problems, where they show that it is Graph Isomorphism hard.

Source Link

The fact that the underlying polytope $Ax \le b$ is the same for $P_1$ and $P_2$ does not matter, unless we know something specific about $A$ and $b$. This is because a general polytope is an affine projection of a simplex (see, for instance, Ziegler's "Lectures for Polytopes", Theorem 2.15). Thus, if $A$ and $b$ encode a simplex, your question is equivalent to asking how hard general polytope isomorphism is. A quick search reveals the following paper by Kaibel and Schwartz On the Complexity of Polytope Isomorphism Problems, where they show that it is Graph Isomorphism hard.