The Hairy Ball problem is PPAD-complete

Journal article

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 (a) computing an approximate zero is PPAD-complete, and (b) computing an exact zero is FIXP-hard. We also consider the Hairy Ball Theorem on toroidal instead of spherical domains and show that the approximate problem remains PPAD-complete. On a conceptual level, our PPAD-membership results are particularly interesting, because they heavily rely on the investigation of multiple-source variants of END-OF-LINE, the canonical PPAD-complete problem. Our results on these new END-OF-LINE variants 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.

Authors: Goldberg, PW; Hollender, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Journal of Computer and System Sciences More from this journal
• Volume: 122
• Pages: 34-62
• Publication date: 2021-06-09
• Acceptance date: 2021-05-26
• DOI: 10.1016/j.jcss.2021.05.004
• EISSN: 1090-2724
• ISSN: 0022-0000
• Language: English
• Keywords: FFR; PPAD; end-of-line; TFNP; computational complexity