Smoothing the gap between NP and ER
- Jeff Erickson,
- ,
- Tillmann Miltzow
- University of Illinois,
- Utrecht University
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-reviewPublication Information
Output type
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-reviewOriginal language
EnglishPages from-to (Number of pages)
Pages 1022-1033 (12 pages)Publication milestones
- Published - 2020
Publication status
Published - 2020
Publisher
IEEE, United StatesPublication IDs
- Scopus: 85100347472
Host publication title
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)Abstract
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.
Publication metrics
PlumX, opens in new tab
Captures
12
Citations
34
Access to documents
Related Event
Title
Foundations of Computer Science
Event type
ConferenceDate
14/12/2020 - 17/12/2020Location
SydneyAustralia