Dynamic Toolbox for ETRINV

December 18, 2019 ยท The Ethereal ยท ๐Ÿ› arXiv.org

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Mikkel Abrahamsen, Tillmann Miltzow arXiv ID 1912.08674 Category cs.CC: Computational Complexity Cross-listed cs.CG, cs.DS Citations 6 Venue arXiv.org Last Checked 6 months ago
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.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Computational Complexity