Completeness for the complexity class R and area-universality

Abstract: Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class

e x i s t s m a t h b b R

plays a crucial role in the study of geometric problems. Sometimes

e x i s t s m a t h b b 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,

e x i s t s m a t h b b R

deals with existentially quantified real variables. In analogy to

P i_{2}^{p}

and

S i g m a_{2}^{p}

in the famous polynomial hierarchy, we study the complexity classes

f o r a l l e x i s t s m a t h b b R

and

e x i s t s f o r a l l m a t h b b 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

f o r a l l e x i s t s m a t h b b R

-complete and support this conjecture by proving

e x i s t s m a t h b b R

- and

f o r a l l e x i s t s m a t h b b R

-completeness of two variants of area-universality. To this end, we introduce tools to prove

f o r a l l e x i s t s m a t h b b R

-hardness and membership. Finally, we present geometric problems as candidates for

f o r a l l e x i s t s m a t h b b R

-complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.

Cites work

Cited in

(6)

This page was built for publication: Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality