# A Universality Theorem for Nested Polytopes

arXiv: https://arxiv.org/abs/1908.02213 · HTML: https://mlsanity.com/paper/1908.02213/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2019.

## Built on by (most cited first, 4 of 4)

- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [On Classifying Continuous Constraint Satisfaction Problems](https://mlsanity.com/paper/2106.02397/) (2021)
- [Covering Polygons is Even Harder](https://mlsanity.com/paper/2106.02335/) (2021)
- [Training Neural Networks is existsmathbb R-complete](https://mlsanity.com/paper/2102.09798/) (2021)

## Abstract (arXiv)

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.