The Hairy Ball Problem is PPAD-Complete.

DOI10.4230/LIPICS.ICALP.2019.65MaRDI QIDQ5091222zbMATH OpenOpenAlexFDO

Authors Paul W. Goldberg, Alexandros Hollender

Publication date 21 July 2022

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/10641/pdf/LIPIcs-ICALP-2019-65.pdf/

zbMATH Keywords

computational complexityend-of-linePPADTFNP

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• The Hairy Ball problem is PPAD-complete
• On the complexity of 2D discrete fixed point problem
• A Sperner lemma complete for PPA
• \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
• On the Complexity of 2D Discrete Fixed Point Problem

Cites work

• A converse to Banach's fixed point theorem and its CLS-completeness
• A Proof of the Hairy Ball Theorem
• An Extremely Short Proof of the Hairy Ball Theorem
• Analytic Proofs of the "Hairy Ball Theorem" and the Brouwer Fixed Point Theorem
• Another short proof of the hairy ball theorem
• Consensus halving is PPA-complete
• scientific article; zbMATH DE number 3562121 (Why is no real title available?)
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• On the complexity of 2D discrete fixed point problem
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• On Two Classical Theorems of Algebraic Topology
• Propositional proofs and reductions between NP search problems
• Reducibility among fractional stability problems
• Settling the complexity of computing two-player Nash equilibria
• The complexity of computing a Nash equilibrium
• The Hairy Ball Theorem via Sperner's Lemma
• The relative complexity of NP search problems
• Towards a unified complexity theory of total functions

Cited in

(6)

• The complexity of the parity argument with potential
• The Hairy Ball problem is PPAD-complete
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• Computational complexity of the -Ham-Sandwich problem
• The complexity of finding fair independent sets in cycles

This page was built for publication: The Hairy Ball Problem is PPAD-Complete.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091222)