Goldberg, Paul W. ;
Hollender, Alexandros
The Hairy Ball Problem is PPADComplete
Abstract
The Hairy Ball Theorem states that every continuous tangent vector field on an evendimensional sphere must have a zero. We prove that the associated computational problem of computing an approximate zero is PPADcomplete. We also give a FIXPhardness result for the general exact computation problem.
In order to show that this problem lies in PPAD, we provide new results on multiplesource variants of EndofLine, the canonical PPADcomplete problem. In particular, finding an approximate zero of a Hairy Ball vector field on an evendimensional sphere reduces to a 2source EndofLine 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(g1)source EndofLine problem.
These multiplesource EndofLine 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 PPADcompleteness for the Imbalance problem defined by Beame et al. in 1998.
BibTeX  Entry
@InProceedings{goldberg_et_al:LIPIcs:2019:10641,
author = {Paul W. Goldberg and Alexandros Hollender},
title = {{The Hairy Ball Problem is PPADComplete}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {65:165:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10641},
URN = {urn:nbn:de:0030drops106416},
doi = {10.4230/LIPIcs.ICALP.2019.65},
annote = {Keywords: Computational Complexity, TFNP, PPAD, EndofLine}
}
2019
Keywords: 

Computational Complexity, TFNP, PPAD, EndofLine 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

2019 