Completeness for the Complexity Class ∀ ∃ R and Area-Universality

Michael Gene Dobbins; Linda Kleist; Tillmann Miltzow; Pawel Rzazewski

doi:10.1007/s00454-022-00381-0

Completeness for the Complexity Class ∀ ∃ R and Area-Universality

Michael Gene Dobbins, Linda Kleist, Tillmann Miltzow, Pawel Rzazewski

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class ∃R
plays a crucial role in the study of geometric problems. Sometimes ∃R
is referred to as the ‘real analog’ of NP. While NP is a class of computational problems that deals with existentially quantified boolean variables, ∃R
deals with existentially quantified real variables. In analogy to Πp2
and Σp2
in the famous polynomial hierarchy, we study the complexity classes ∀∃R
and ∃∀R
with real variables. Our main interest is the AREA UNIVERSALITY problem, where we are given a plane graph G, and ask if for each assignment of areas to the inner faces of G, there exists a straight-line drawing of G realizing the assigned areas. We conjecture that AREA UNIVERSALITY is ∀∃R
-complete and support this conjecture by proving ∃R
- and ∀∃R
-completeness of two variants of AREA UNIVERSALITY. To this end, we introduce tools to prove ∀∃R
-hardness and membership. Finally, we present geometric problems as candidates for ∀∃R
-complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.

Original language	English
Pages (from-to)	154-188
Number of pages	35
Journal	Discrete and Computational Geometry
Volume	70
Issue number	1
DOIs	https://doi.org/10.1007/s00454-022-00381-0
Publication status	Published - Jul 2023

Keywords

Complexity class
Existential theory of the reals
Universal existential theory of the reals
Planar graph
Face area
Area-universality

Access to Document

10.1007/s00454-022-00381-0Licence: CC BY

s00454-022-00381-0Final published version, 937 KBLicence: CC BY

Cite this

@article{104bf8ad546346bb8d3ee616fd4b4993,

title = "Completeness for the Complexity Class ∀ ∃ R and Area-Universality",

abstract = "Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class ∃R plays a crucial role in the study of geometric problems. Sometimes ∃R is referred to as the {\textquoteleft}real analog{\textquoteright} of NP. While NP is a class of computational problems that deals with existentially quantified boolean variables, ∃R deals with existentially quantified real variables. In analogy to Πp2 and Σp2 in the famous polynomial hierarchy, we study the complexity classes ∀∃R and ∃∀R with real variables. Our main interest is the AREA UNIVERSALITY problem, where we are given a plane graph G, and ask if for each assignment of areas to the inner faces of G, there exists a straight-line drawing of G realizing the assigned areas. We conjecture that AREA UNIVERSALITY is ∀∃R-complete and support this conjecture by proving ∃R- and ∀∃R-completeness of two variants of AREA UNIVERSALITY. To this end, we introduce tools to prove ∀∃R-hardness and membership. Finally, we present geometric problems as candidates for ∀∃R-complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.",

keywords = "Complexity class, Existential theory of the reals, Universal existential theory of the reals, Planar graph, Face area, Area-universality",

author = "Dobbins, {Michael Gene} and Linda Kleist and Tillmann Miltzow and Pawel Rzazewski",

note = "Funding Information: A preliminary version appears in the proceedings of WG 2018 []. Moreover, a video presenting this paper is available at https://youtu.be/OQkACiNS66o . Tillmann Miltzow was generously supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 016.Veni.192.250. Pawe{\l} Rz{\c a}{\.z}ewski was supported by the ERC Starting Grant CUTACOMBS (Grant Agreement No. 714704) Publisher Copyright: {\textcopyright} 2022, The Author(s).",

year = "2023",

month = jul,

doi = "10.1007/s00454-022-00381-0",

language = "English",

volume = "70",

pages = "154--188",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Completeness for the Complexity Class ∀ ∃ R and Area-Universality

AU - Dobbins, Michael Gene

AU - Kleist, Linda

AU - Miltzow, Tillmann

AU - Rzazewski, Pawel

N1 - Funding Information: A preliminary version appears in the proceedings of WG 2018 []. Moreover, a video presenting this paper is available at https://youtu.be/OQkACiNS66o . Tillmann Miltzow was generously supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 016.Veni.192.250. Paweł Rzążewski was supported by the ERC Starting Grant CUTACOMBS (Grant Agreement No. 714704) Publisher Copyright: © 2022, The Author(s).

PY - 2023/7

Y1 - 2023/7

N2 - Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class ∃R plays a crucial role in the study of geometric problems. Sometimes ∃R is referred to as the ‘real analog’ of NP. While NP is a class of computational problems that deals with existentially quantified boolean variables, ∃R deals with existentially quantified real variables. In analogy to Πp2 and Σp2 in the famous polynomial hierarchy, we study the complexity classes ∀∃R and ∃∀R with real variables. Our main interest is the AREA UNIVERSALITY problem, where we are given a plane graph G, and ask if for each assignment of areas to the inner faces of G, there exists a straight-line drawing of G realizing the assigned areas. We conjecture that AREA UNIVERSALITY is ∀∃R-complete and support this conjecture by proving ∃R- and ∀∃R-completeness of two variants of AREA UNIVERSALITY. To this end, we introduce tools to prove ∀∃R-hardness and membership. Finally, we present geometric problems as candidates for ∀∃R-complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.

AB - Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class ∃R plays a crucial role in the study of geometric problems. Sometimes ∃R is referred to as the ‘real analog’ of NP. While NP is a class of computational problems that deals with existentially quantified boolean variables, ∃R deals with existentially quantified real variables. In analogy to Πp2 and Σp2 in the famous polynomial hierarchy, we study the complexity classes ∀∃R and ∃∀R with real variables. Our main interest is the AREA UNIVERSALITY problem, where we are given a plane graph G, and ask if for each assignment of areas to the inner faces of G, there exists a straight-line drawing of G realizing the assigned areas. We conjecture that AREA UNIVERSALITY is ∀∃R-complete and support this conjecture by proving ∃R- and ∀∃R-completeness of two variants of AREA UNIVERSALITY. To this end, we introduce tools to prove ∀∃R-hardness and membership. Finally, we present geometric problems as candidates for ∀∃R-complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.

KW - Complexity class

KW - Existential theory of the reals

KW - Universal existential theory of the reals

KW - Planar graph

KW - Face area

KW - Area-universality

UR - http://www.scopus.com/inward/record.url?scp=85130271112&partnerID=8YFLogxK

U2 - 10.1007/s00454-022-00381-0

DO - 10.1007/s00454-022-00381-0

M3 - Article

SN - 0179-5376

VL - 70

SP - 154

EP - 188

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

Completeness for the Complexity Class ∀ ∃ R and Area-Universality

Abstract

Keywords

Access to Document

Fingerprint

Cite this