Id: arxiv/2611.25164 Url: https://arxiv.org/abs/2611.25164 Tags: cs.CG, cs.CC, math.CO, math.MG Score: 0 Title: Convexity is overrated: Shortest paths on 4-polytopes are hard to compute Domain: cs.CG Source: arxiv Authors: Igor Pak Reviews: 0 Subject: cs.CG Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-18 Page: https://delphi.science/r/arxiv/2611.25164 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.