6
$\begingroup$
  1. Where is the complexity of the problem 'Given two bounded compact convex integral polyhedra in $\mathbb R^n$ presented by $O(poly(n))$ integer valued halfspaces given by linear inequalities with coefficients of size $O(poly(n))$ bits with promise that they are equal volume is there a scissors congruence between them?' in the complexity hierarchy?

Is there efficient algorithm?

  1. What if we drop the promise?

Where it stands with respect to Hilbert`s Third

Hilbert third asks if two volume equal polytopes are scissors congruent. Computing volume is not in $PH$ is the belief. Complexity version of Hilbert`s Third then is asking for scissors congruence given volume oracle. So we assume in the problem 1. the volumes are equal.

Perhaps if volume oracle does anything then problem 2. has no chance of being in $PH$. If the volumes were equal and they are not scissors congruent perhaps there is an $NP$ witness which will reveal they cannot be scissors congruent. The same witness might also tell if they are not scissors congruent even if volumes are equal.

$\endgroup$
4
  • 1
    $\begingroup$ I'm trying to understand the 3- or 4-dimensional case. There we know that the Dehn invariant controls scissors congruence once we have equal volume. So the question reduces to compute the Dehn invariant (sum over all edges of length tensor angle between adjacent faces) and decide if the Dehn invariants agree in $\mathbb{R}\otimes \mathbb{R}/\mathbb{Z}$. So there is a complexity issue concerning the number of edges and another issue of deciding when two real numbers are the same. I'm not sure if this is related to what you had in mind. $\endgroup$ Commented Jul 6, 2019 at 18:30
  • 1
    $\begingroup$ And of course, in dimensions $\geq 5$ we don't know that scissors congruence is controlled by the Dehn invariant, so that approach fails for higher dimensions. $\endgroup$ Commented Jul 6, 2019 at 18:31
  • $\begingroup$ @MatthiasWendt Dehn invariant is not the only way. I believe there are other approaches. So 'we know that the Dehn invariant....' could be true, However is it necessary to invoke Dehn invariants? $\endgroup$
    – Turbo
    Commented Jul 6, 2019 at 18:52
  • 1
    $\begingroup$ @MatthiasWendt 1. Ciesielska, Danuta; Ciesielski, Krzysztof (2018-05-29). "Equidecomposability of Polyhedra: A Solution of Hilbert's Thirda Problem in Kraków before ICM 1900". The Mathematical Intelligencer. 40 (2): 55–63. and 2. trungtuan.files.wordpress.com/2007/08/8-2007.pdf. $\endgroup$
    – Turbo
    Commented Jul 6, 2019 at 19:07

0

You must log in to answer this question.