- 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?
- 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.