{"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","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-18","reactions":{}}