Document Open Access Logo

The Hairy Ball Problem is PPAD-Complete

Authors Paul W. Goldberg , Alexandros Hollender

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.65.pdf
  • Filesize: 463 kB
  • 14 pages

Document Identifiers

Author Details

Paul W. Goldberg
  • Department of Computer Science, University of Oxford, United Kingdom
Alexandros Hollender
  • Department of Computer Science, University of Oxford, United Kingdom

Funding

  • Hollender, Alexandros: Supported by an EPSRC doctoral studentship (Reference 1892947).

Cite As Get BibTex

Paul W. Goldberg and Alexandros Hollender. The Hairy Ball Problem is PPAD-Complete. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 65:1-65:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.65

Abstract

The Hairy Ball Theorem states that every continuous tangent vector field on an even-dimensional sphere must have a zero. We prove that the associated computational problem of computing an approximate zero is PPAD-complete. We also give a FIXP-hardness result for the general exact computation problem.
In order to show that this problem lies in PPAD, we provide new results on multiple-source variants of End-of-Line, the canonical PPAD-complete problem. In particular, finding an approximate zero of a Hairy Ball vector field on an even-dimensional sphere reduces to a 2-source End-of-Line problem. If the domain is changed to be the torus of genus g >= 2 instead (where the Hairy Ball Theorem also holds), then the problem reduces to a 2(g-1)-source End-of-Line problem.
These multiple-source End-of-Line results are of independent interest and provide new tools for showing membership in PPAD. In particular, we use them to provide the first full proof of PPAD-completeness for the Imbalance problem defined by Beame et al. in 1998.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Computational Complexity
  • TFNP
  • PPAD
  • End-of-Line

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. James Aisenberg, Maria Luisa Bonet, and Sam Buss. 2-D Tucker is PPA complete. Technical Report TR15-163, ECCC, 2015. Google Scholar
  2. Stefan Banach. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fundamenta Mathematicae, 3(1):133-181, 1922. Google Scholar
  3. Paul Beame, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. The relative complexity of NP search problems. Journal of Computer and System Sciences, 57(1):3-19, 1998. Google Scholar
  4. W. M. Boothby. On two classical theorems of algebraic topology. The American Mathematical Monthly, 78(3):237-249, 1971. Google Scholar
  5. L. E. J. Brouwer. Über Abbildung von Mannigfaltigkeiten. Mathematische Annalen, 71:97-115, 1912. Google Scholar
  6. Samuel R. Buss and Alan S. Johnson. Propositional proofs and reductions between NP search problems. Annals of Pure and Applied Logic, 163(9):1163-1182, 2012. Google Scholar
  7. Xi Chen and Xiaotie Deng. On the complexity of 2D discrete fixed point problem. Theoretical Computer Science, 410(44):4448-4456, 2009. Google Scholar
  8. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3):1-57, 2009. Google Scholar
  9. Eugene Curtin. Another Short Proof of the Hairy Ball Theorem. The American Mathematical Monthly, 125(5):462-463, 2018. Google Scholar
  10. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009. Google Scholar
  11. Constantinos Daskalakis and Christos H. Papadimitriou. Continuous local search. In 22nd SODA, pages 790-804. SIAM, 2011. Google Scholar
  12. Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis. A converse to Banach’s fixed point theorem and its CLS-completeness. In 50th STOC, pages 44-50. ACM, 2018. Google Scholar
  13. Xiaotie Deng, Qi Qi, and Amin Saberi. Algorithmic solutions for envy-free cake cutting. Operations Research, 60(6):1461-1476, 2012. Google Scholar
  14. Murray Eisenberg and Robert Guy. A Proof of the Hairy Ball Theorem. The American Mathematical Monthly, 86(7):571-574, 1979. Google Scholar
  15. Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria and other fixed points. SIAM Journal on Computing, 39(6):2531-2597, 2010. Google Scholar
  16. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. End of Potential Line. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.03450.
  17. Aris Filos-Ratsikas and Paul W. Goldberg. Consensus Halving is PPA-complete. In 50th STOC, pages 51-64. ACM, 2018. Google Scholar
  18. Aris Filos-Ratsikas and Paul W. Goldberg. The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches. arXiv preprint, 2018. (to appear at STOC 2019). URL: http://arxiv.org/abs/1805.12559.
  19. Paul W. Goldberg and Christos H. Papadimitriou. Towards a unified complexity theory of total functions. Journal of Computer and System Sciences, 94:167-192, 2018. Google Scholar
  20. Victor Guillemin and Alan Pollack. Differential topology. Prentice-Hall, 1974. Google Scholar
  21. Alexandros Hollender and Paul W. Goldberg. The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard. Technical Report TR18-120, ECCC, 2018. Google Scholar
  22. Tyler Jarvis and James Tanton. The Hairy Ball Theorem via Sperner’s Lemma. American Mathematical Monthly, pages 599-603, 2004. Google Scholar
  23. Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, and Shang-Hua Teng. Reducibility among Fractional Stability Problems. SIAM Journal on Computing, 42(6):2063-2113, 2013. Google Scholar
  24. Peter McGrath. An extremely short proof of the hairy ball theorem. The American Mathematical Monthly, 123(5):502-503, 2016. Google Scholar
  25. Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317-324, 1991. Google Scholar
  26. John Milnor. Analytic proofs of the “hairy ball theorem” and the Brouwer fixed point theorem. The American Mathematical Monthly, 85(7):521-524, 1978. Google Scholar
  27. Christos H. Papadimitriou. On graph-theoretic lemmata and complexity classes. In 31st FOCS, pages 794-801. IEEE, 1990. Google Scholar
  28. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-532, 1994. Google Scholar
  29. Henri Poincaré. Sur les courbes définies par les équations différentielles. Journal de Mathématiques Pures et Appliquées, 4:167-244, 1885. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact