# Smoothing the gap between NP and ER

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

## Key facts

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

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

- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation](https://mlsanity.com/paper/2102.06635/) (2021)
- [List-Decodable Covariance Estimation](https://mlsanity.com/paper/2206.10942/) (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)
- [On Probabilistic and Causal Reasoning with Summation Operators](https://mlsanity.com/paper/2405.03069/) (2024)
- [The Limits of Tractable Marginalization](https://mlsanity.com/paper/2506.12020/) (2025)
- [Probabilistic and Causal Satisfiability: Constraining the Model](https://mlsanity.com/paper/2504.19944/) (2025)
- [Training Neural Networks is existsmathbb R-complete](https://mlsanity.com/paper/2102.09798/) (2021)
- [Approaching I/O-optimality for Approximate Attention](https://mlsanity.com/paper/2605.23751/) (2026)

## Abstract (arXiv)

We study algorithmic problems that belong to the complexity class of the existential theory of the reals (ER). A problem is ER-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 ER is often called a real RAM analogue of NP, since the problem ETR can be viewed as the real-valued variant of SAT. In this paper we prove a real RAM analogue to the Cook-Levin theorem which shows that ER membership is equivalent to having a verification algorithm that runs in polynomial-time on a real RAM. This gives an easy proof of ER-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 ER-complete problems under smoothed analysis. We show that for a wide class of ER-complete problems, its witness can be represented with logarithmic input-precision by using smoothed analysis on its real RAM verification algorithm. This shows in a formal way that the boundary between NP and ER (formed by inputs whose solution witness needs high input-precision) consists of contrived input. We apply our framework to well-studied ER-complete recognition problems which have the exponential bit phenomenon such as the recognition of realizable order types or the Steinitz problem in fixed dimension.