2026-10-11T13:26:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6303 2024-03-06T09:37:40Z ddc:004 open_access

The Complexity of Hex and the Jordan Curve Theorem Adler, Aviv Daskalakis, Constantinos Demaine, Erik D. Jordan Brouwer Hex PPAD PSPACE The Jordan curve theorem and Brouwer's fixed-point theorem are fundamental problems in topology. We study their computational relationship, showing that a stylized computational version of Jordan’s theorem is PPAD-complete, and therefore in a sense computationally equivalent to Brouwer’s theorem. As a corollary, our computational result implies that these two theorems directly imply each other mathematically, complementing Maehara's proof that Brouwer implies Jordan [Maehara, 1984]. We then turn to the combinatorial game of Hex which is related to Jordan's theorem, and where the existence of a winner can be used to show Brouwer's theorem [Gale,1979]. We establish that determining who won an (implicitly encoded) play of Hex is PSPACE-complete by adapting a reduction (due to Goldberg [Goldberg,2015]) from Quantified Boolean Formula (QBF). As this problem is analogous to evaluating the output of a canonical path-following algorithm for finding a Brouwer fixed point - and which is known to be PSPACE-complete [Goldberg/Papadimitriou/Savani, 2013] - we thereby establish a connection between Brouwer, Jordan and Hex higher in the complexity hierarchy. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aviv Adler and Constantinos Daskalakis and Erik D. Demaine 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.24 urn:nbn:de:0030-drops-63032 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.24 eng https://creativecommons.org/licenses/by/3.0/legalcode