Smoothing the gap between NP and ER

DOI10.1109/FOCS46700.2020.00099MaRDI QIDQ6943956zbMATH OpenFDO

Authors Jeff Erickson, Tillmann Miltzow, Ivor van der Hoog

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS46700.2020.00099

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(5)

• Geometric embeddability of complexes is \(\exists\mathbb{R}\)-complete
• Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete
• Pizza sharing is PPA-hard
• Recognition of unit segment and polyline graphs is \(\exists \mathbb{R} \)-complete
• The complexity of recognizing geometric hypergraphs

This page was built for publication: Smoothing the gap between NP and ER

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6943956)