Dynamic Toolbox for ETRINV

Mikkel Abrahamsen, Tillmann Miltzow

Research output: Working paperPreprintAcademic

Abstract

Recently, various natural algorithmic problems have been shown to be $\exists \mathbb{R}$-complete. The reduction relied in many cases on the $\exists \mathbb{R}$-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.
Original languageEnglish
PublisherarXiv
Number of pages19
DOIs
Publication statusPublished - 18 Dec 2019

Bibliographical note

19 pages, 3 figures

Keywords

  • cs.CC
  • cs.CG
  • cs.DS

Fingerprint

Dive into the research topics of 'Dynamic Toolbox for ETRINV'. Together they form a unique fingerprint.

Cite this