0
$\begingroup$

Consider you have two (possibly same) convex $1$-skeleton of a regular graph $A$ and $B$ in $m$-dimensions inscribed in a sphere with possibly exponential number of vertices in $n$-dimension with promise that either every vertex is same or every vertex is distinct (the polyhedra could still overlap). If $m<n$ we can assume they just live on a hyperplane with vertices on the sphere.

You have to decide with probability $>2/3$ whether $A$ and $B$ are same.

You do not have the polyhedron as explicit inputs since they could have exponentially large number of vertices.

You have an oracle access that you can use polynomially (in $n$) many number of times to get random samples of vertex coordinates and neighbor coordinates which are connected by a $1$-dimensional edge.

Would there be any way to decide at all with probability $>2/3$ that the two polyhedrons are distinct in polynomial in $n$ time?

Assume coordinates of polytopes have vertex coordinates from finitely many bounded integer values (say from $0$ to $c$).


I think the fact that I have convex $1$-skeleton of a regular graph seems to make that the only non-trivial configuration would be one is rotation of other.

$\endgroup$
  • $\begingroup$ what do you mean by "random sample of vertices". What is the input and output of a call of the oracle? $\endgroup$ – Moritz Firsching Mar 10 '16 at 18:34
  • $\begingroup$ @MoritzFirsching Input is 'please reveal me at random number $r$' and oracle output would be '$r$th vertex coordinates and neighbors coordinates'. $\endgroup$ – user76479 Mar 10 '16 at 18:36
  • $\begingroup$ There are only 3 regular polytopes in any dimension: the simplex, the hypercube, and the orthoplex (a.k.a. cross polytope). So I think the answer is trivially Yes. $\endgroup$ – Joseph O'Rourke Mar 10 '16 at 19:01
  • 1
    $\begingroup$ The condition of regularity on polytopes is extremely strong. My guess is that you mean the 1-skeleton is a regular graph instead. $\endgroup$ – Douglas Zare Mar 10 '16 at 19:02
  • $\begingroup$ @DouglasZare Yes that is what I mean. $\endgroup$ – user76479 Mar 10 '16 at 19:03

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy