The Hairy Ball problem is PPAD-complete

DOI10.1016/J.JCSS.2021.05.004MaRDI QIDQ2229948zbMATH OpenOpenAlexWikidataFDO

Authors Paul W. Goldberg, Alexandros Hollender

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, https://drops.dagstuhl.de/opus/volltexte/2019/10641/

zbMATH Keywords

computational complexityPPADTFNPend-of-line

Mathematics Subject Classification ID

Computer science (68-XX)

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

• scientific article; zbMATH DE number 3562121 (Why is no real title available?)
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• 2-D Tucker is PPA complete
• A Proof of the Hairy Ball Theorem
• A converse to Banach's fixed point theorem and its CLS-completeness
• Algorithmic solutions for envy-free cake cutting
• 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
• Inapproximability of Nash equilibrium
• On Two Classical Theorems of Algebraic Topology
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of 2D discrete fixed point problem
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Propositional proofs and reductions between NP search problems
• Reducibility among fractional stability problems
• Settling the complexity of computing two-player Nash equilibria
• The Hairy Ball Theorem via Sperner's Lemma
• The complexity of computing a Nash equilibrium
• The complexity of splitting necklaces and bisecting ham sandwiches
• The computation of fixed points and applications
• The relative complexity of NP search problems
• Towards a unified complexity theory of total functions

Cited in

(9)

• On the Complexity of Equilibrium Computation in First-Price Auctions
• The complexity of gradient descent: CLS = PPAD \(\cap\) pls
• Discrete versions of the KKM lemma and their PPAD-completeness
• Financial networks with singleton liability priorities
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• Consensus-Halving: Does It Ever Get Easier?
• Financial networks with singleton liability priorities
• The complexity of finding fair independent sets in cycles
• Further collapses in \(\mathsf{TFNP}\)

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 Q2229948)