A Universality Theorem for Nested Polytopes

In a nutshell, we show that polynomials and nested polytopes are topological, algebraic and algorithmically equivalent. Given two polytops Asubseteq B and a number k, the Nested Polytope Problem (NPP) asks, if there exists a polytope X on k vertices such that Asubseteq X subseteq B. The polytope A is given by a set of vertices and the polytope B is given by the defining hyperplanes. We show a universality theorem for NPP. Given an instance I of the NPP, we define the solutions set of I as V'(I) = (x1,ldots,xk)∈ ℝk· n : Asubseteq conv(x1,ldots,xk) subseteq B. As there are many symmetries, induced by permutations of the vertices, we will consider the normalized solution space V(I). Let F be a finite set of polynomials, with bounded solution space. Then there is an instance I of the NPP, which has a rationally-equivalent normalized solution space V(I). Two sets V and W are rationally equivalent if there exists a homeomorphism f : V rightarrow W such that both f and f-1 are given by rational functions. A function f:Vrightarrow W is a homeomorphism, if it is continuous, invertible and its inverse is continuous as well. As a corollary, we show that NPP is exists ℝ-complete. This implies that unless exists ℝ = NP, the NPP is not contained in the complexity class NP. Note that those results already follow from a recent paper by Shitov. Our proof is geometric and arguably easier.