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

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

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

}

TY - GEN

T1 - Smoothing the gap between NP and ER

AU - Erickson, Jeff

AU - van der Hoog, Ivor

AU - Miltzow, Tillmann

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

ER -

Smoothing the gap between NP and ER

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater