Smoothing the gap between NP and ER

Jeff Erickson; Ivor van der Hoog; Tillmann Miltzow

doi:10.1109/FOCS46700.2020.00099

Smoothing the gap between NP and ER

Jeff Erickson
, Ivor van der Hoog
, Tillmann Miltzow

University of Illinois at Chicago
Utrecht University

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

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.

Originalsprog	Engelsk
Titel	2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
Antal sider	12
Forlag	IEEE
Publikationsdato	2020
Sider	1022-1033
DOI	https://doi.org/10.1109/FOCS46700.2020.00099
Status	Udgivet - 2020
Udgivet eksternt	Ja
Begivenhed	Foundations of Computer Science - Sydney, Australien Varighed: 14 dec. 2020 → 17 dec. 2020 Konferencens nummer: 61

Konference

Konference	Foundations of Computer Science
Nummer	61
Land/Område	Australien
By	Sydney
Periode	14/12/2020 → 17/12/2020

Adgang til dokumentet

10.1109/FOCS46700.2020.00099

Citationsformater

@inproceedings{ffdfd3946ff543ca8762c7d052a8605a,

title = "Smoothing the gap between NP and ER",

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. ",

keywords = "Existential Theory of the Real Numbers, ER-complete, ETR, Real RAM, Computational Complexity",

author = "Jeff Erickson and \{van der Hoog\}, Ivor and Tillmann Miltzow",

year = "2020",

doi = "10.1109/FOCS46700.2020.00099",

language = "English",

pages = "1022--1033",

booktitle = "2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)",

publisher = "IEEE",

address = "United States",

note = " Foundations of Computer Science ; Conference date: 14-12-2020 Through 17-12-2020",

}

TY - GEN

T1 - Smoothing the gap between NP and ER

AU - Erickson, Jeff

AU - van der Hoog, Ivor

AU - Miltzow, Tillmann

N1 - Conference code: 61

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Existential Theory of the Real Numbers

KW - ER-complete

KW - ETR

KW - Real RAM

KW - Computational Complexity

U2 - 10.1109/FOCS46700.2020.00099

DO - 10.1109/FOCS46700.2020.00099

M3 - Article in proceedings

SP - 1022

EP - 1033

BT - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)

PB - IEEE

T2 - Foundations of Computer Science

Y2 - 14 December 2020 through 17 December 2020

ER -

Smoothing the gap between NP and ER

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater