The Hairy Ball Problem is PPAD-Complete.

DOI10.4230/LIPIcs.ICALP.2019.65OpenAlexW3172271059MaRDI QIDQ5091222

Alexandros Hollender, Paul W. Goldberg

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 complexityTFNPPPADend-of-line

Mathematics Subject Classification ID

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

Related Items (3)

The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ The complexity of the parity argument with potential

Cites Work

• Unnamed Item
• Unnamed Item
• Propositional proofs and reductions between NP search problems
• On total functions, existence theorems and computational complexity
• On the complexity of 2D discrete fixed point problem
• The relative complexity of NP search problems
• On the complexity of the parity argument and other inefficient proofs of existence
• Towards a unified complexity theory of total functions
• On the Complexity of Nash Equilibria and Other Fixed Points
• Settling the complexity of computing two-player Nash equilibria
• The Hairy Ball Theorem via Sperner's Lemma
• A Proof of the Hairy Ball Theorem
• Analytic Proofs of the "Hairy Ball Theorem" and the Brouwer Fixed Point Theorem
• An Extremely Short Proof of the Hairy Ball Theorem
• Another Short Proof of the Hairy Ball Theorem
• The Complexity of Computing a Nash Equilibrium
• A converse to Banach's fixed point theorem and its CLS-completeness
• Consensus halving is PPA-complete
• Reducibility among Fractional Stability Problems
• On Two Classical Theorems of Algebraic Topology

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