2026-08-11T04:47:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10641 2024-03-06T10:46:21Z ddc:004 open_access

The Hairy Ball Problem is PPAD-Complete Goldberg, Paul W. Hollender, Alexandros Computational Complexity TFNP PPAD End-of-Line 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paul W. Goldberg and Alexandros Hollender 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.65 urn:nbn:de:0030-drops-106416 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.65 eng https://creativecommons.org/licenses/by/3.0/legalcode