The Hairy Ball problem is PPAD-complete

DOI10.1016/j.jcss.2021.05.004OpenAlexW2965985967WikidataQ113398676 ScholiaQ113398676MaRDI QIDQ2229948

Alexandros Hollender, Paul W. Goldberg

Publication date: 17 September 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1902.07657

zbMATH Keywords

computational complexityTFNPPPADend-of-line

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items (7)

On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ Consensus-Halving: Does It Ever Get Easier? ⋮ Financial networks with singleton liability priorities ⋮ Financial networks with singleton liability priorities ⋮ The complexity of finding fair independent sets in cycles ⋮ Discrete versions of the KKM lemma and their PPAD-completeness ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

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 computation of fixed points and applications
• 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
• 2-D Tucker is PPA complete
• 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
• Inapproximability of Nash Equilibrium
• An Extremely Short Proof of the Hairy Ball Theorem
• Another Short Proof of the Hairy Ball Theorem
• Algorithmic Solutions for Envy-Free Cake Cutting
• The Complexity of Computing a Nash Equilibrium
• The complexity of splitting necklaces and bisecting ham sandwiches
• 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