학술

Convexity is overrated: Shortest paths on 4-polytopes are hard to compute

arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.

Abstract

We prove that computing geodesic distance on the boundary of a rational convex $4$-polytope is NP-hard. We then construct rational $4$-polytopes with two rational points joined by exponentially many shortest paths of equal rational length, disproving several conjectures along the way. For the same problem, we also prove SQRTSUM-hardness under deterministic polynomial-time Turing reductions. By a separate argument, we show that the square of the geodesic distance between distinct rational boundary points of a rational convex polytope is a totally positive multiquadratic number.
Additional Features

관련 뉴스