Dynamic Toolbox for ETRINV
Not on the map. Why?
Abstract (arXiv)
Recently, various natural algorithmic problems have been shown to be exists ℝ-complete. The reduction relied in many cases on the exists ℝ-completeness of the problem ETR-INV, which served as a useful intermediate problem. Often some strengthening and modification of ETR-INV was required. This lead to a cluttered situation where no paper included all the previous details. Here, we give a streamlined exposition in a self-contained manner. We also explain and prove various universality results regarding ETR-INV. These notes should not be seen as a research paper with new results. However, we do describe some refinements of earlier results which might be useful for future research. We plan to extend and update this exposition as seems fit.
Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). First posted on arXiv 18 Dec 2019.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1; 2022: 1; 2023: 0; 2024: 0; 2025: 0; 2026: 2.
4 papers.
- 2026On the Complexity Gap Between POMDPs and Multi-Environment POMDPs10 Oct 2026
- 2026Security Properties of Neural Networks as Decision Problems30 Sep 2026
- 2022Training Fully Connected Neural Networks is existsℝ-Complete4 Apr 2022
- 2021On Classifying Continuous Constraint Satisfaction Problems4 Jun 2021