The Complexity of Hex and the Jordan Curve Theorem
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 theore...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Schloss Dagstuhl, Leibniz-Zentrum für Informatik GmbH
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110842 https://orcid.org/0000-0003-3698-7639 https://orcid.org/0000-0002-5451-0490 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826204872106573824 |
|---|---|
| author | Adler, Aviv Daskalakis, Konstantinos Demaine, Erik D |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Adler, Aviv Daskalakis, Konstantinos Demaine, Erik D |
| author_sort | Adler, Aviv |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:02:42Z |
| format | Article |
| id | mit-1721.1/110842 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:02:42Z |
| publishDate | 2017 |
| publisher | Schloss Dagstuhl, Leibniz-Zentrum für Informatik GmbH |
| record_format | dspace |
| spelling | mit-1721.1/1108422022-10-01T12:45:07Z The Complexity of Hex and the Jordan Curve Theorem Adler, Aviv Daskalakis, Konstantinos Demaine, Erik D Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Adler, Aviv Daskalakis, Konstantinos Demaine, Erik D 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. National Science Foundation (U.S.) (NSF grant CCF-1551875) United States. Office of Naval Research (ONR grant N00014-12-1-0999) 2017-07-25T18:31:42Z 2017-07-25T18:31:42Z 2016-07 Article http://purl.org/eprint/type/ConferencePaper 978-3-95977-013-2 1868-8969 Track A: Algorithms, Complexity and Games Article no.24 http://hdl.handle.net/1721.1/110842 Adler, Aviv, Constantinos Daskalakis, and Erik Demaine. "The Complexity of Hex and the Jordan Curve Theorem" In 43rd International Colloquium on Automata, Languages, and Programming: ICALP 2016, Rome, Italy, July 12-15, 2016. Article no. 24; pp. 24:1-24:14. https://orcid.org/0000-0003-3698-7639 https://orcid.org/0000-0002-5451-0490 https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.24 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) Creative Commons Attribution 4.0 International License http://creativecommons.org/licenses/by/4.0/ application/pdf Schloss Dagstuhl, Leibniz-Zentrum für Informatik GmbH Dagstuhl Publishing |
| spellingShingle | Adler, Aviv Daskalakis, Konstantinos Demaine, Erik D The Complexity of Hex and the Jordan Curve Theorem |
| title | The Complexity of Hex and the Jordan Curve Theorem |
| title_full | The Complexity of Hex and the Jordan Curve Theorem |
| title_fullStr | The Complexity of Hex and the Jordan Curve Theorem |
| title_full_unstemmed | The Complexity of Hex and the Jordan Curve Theorem |
| title_short | The Complexity of Hex and the Jordan Curve Theorem |
| title_sort | complexity of hex and the jordan curve theorem |
| url | http://hdl.handle.net/1721.1/110842 https://orcid.org/0000-0003-3698-7639 https://orcid.org/0000-0002-5451-0490 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT adleraviv thecomplexityofhexandthejordancurvetheorem AT daskalakiskonstantinos thecomplexityofhexandthejordancurvetheorem AT demaineerikd thecomplexityofhexandthejordancurvetheorem AT adleraviv complexityofhexandthejordancurvetheorem AT daskalakiskonstantinos complexityofhexandthejordancurvetheorem AT demaineerikd complexityofhexandthejordancurvetheorem |