The Complexity of Hex and the Jordan Curve Theorem

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...

Full description

Bibliographic Details
Main Authors: Adler, Aviv, Daskalakis, Konstantinos, Demaine, Erik D
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
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

Internet

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

Similar Items