A Universality Theorem for Nested Polytopes

MaRDI QIDQ6323267zbMATH OpenFDO

Authors Michael Gene Dobbins, Andreas Holmsen, Tillmann Miltzow

Publication date 6 August 2019

Abstract: In a nutshell, we show that polynomials and nested polytopes are topological, algebraic and algorithmically equivalent. Given two polytops $AsubseteqB$ and a number $k$, the Nested Polytope Problem (NPP) asks, if there exists a polytope $X$ on $k$ vertices such that $AsubseteqXsubseteqB$. 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 ${\displaystyle }$ V'(I) = {(x_1,ldots,x_k)in mathbb{R}^{kcdot n} : Asubseteq ext{conv}(x_1,ldots,x_k) subseteq B}.${\displaystyle }$ As there are many symmetries, induced by permutations of the vertices, we will consider the emph{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:VightarrowW$ such that both $f$ and $f^{-1}$ are given by rational functions. A function $f:VightarrowW$ is a homeomorphism, if it is continuous, invertible and its inverse is continuous as well. As a corollary, we show that NPP is $existsmathbbR$-complete. This implies that unless $existsmathbbR=$ 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.

This page was built for publication: A Universality Theorem for Nested Polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323267)