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 |