Smoothing the gap between NP and ER

We study algorithmic problems that belong to the complexity class of the existential theory of the reals (∃ ). A problem is ∃ -complete if it is as hard as the problem ETR and if it can be written as an ETR formula. Traditionally, these problems are studied in the real RAM, a model of computation that assumes that the storage and comparison of real-valued numbers can be done in constant space and time, with infinite precision. The complexity class ∃ is often called a real RAM analogue of NP, since the problem ETR can be viewed as the real-valued variant of SAT. The real RAM assumption that we can represent and compare arbitrary irrational values in constant space and time is not very realistic. Yet this assumption is vital, since some ∃ -complete problems have an "exponential bit phenomenon" where there exists an input for the problem, such that the witness of the solution requires geometric coordinates which need exponential word size when represented in binary. The problems that exhibit this phenomenon are NP-hard (since ETR is NPhard) but it is unknown if they lie in NP. NP membership is often showed by using the famous Cook-Levin theorem which states that the existence of a polynomial-time verification algorithm for the problem witness is equivalent to NP membership. The exponential bit phenomenon prohibits a straightforward application of the Cook-Levin theorem.

In this paper we first present a result which we believe to be of independent interest: we prove a real RAM analogue to the Cook-Levin theorem which shows that ∃ membership is equivalent to having a verification algorithm that runs in polynomial-time on a real RAM. This gives an easy proof of ∃ -membership, as verification algorithms on a real RAM are much more versatile than ETR-formulas.

We use this result to construct a framework to study ∃ -complete problems under smoothed analysis. We show that for a wide class of ∃ -complete problems, its witness can be represented with logarithmic inputprecision by using smoothed analysis on its real RAM verification algorithm. This shows in a formal way that the boundary between NP and ∃ (formed by inputs whose solution witness needs high input-precision) consists of contrived input.

We apply our framework to well-studied ∃ -complete recognition problems which have the exponential bit phenomenon such as the recognition of realizable order types or the Steinitz problem in fixed dimension. Interestingly our techniques also generalize to problems with a natural notion of resource augmentation (geometric packing, the art gallery problem).