On the complexity of 2D discrete fixed point problem

DOI10.1016/j.tcs.2009.07.052zbMath1183.68294OpenAlexW1826384874MaRDI QIDQ1035680

Xiaotie Deng, Xi Chen

Publication date: 4 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.052

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Unique end of potential line ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Understanding PPA-completeness ⋮ The Hairy Ball problem is PPAD-complete ⋮ 2-D Tucker is PPA complete ⋮ Envy-free cake division without assuming the players prefer nonempty pieces ⋮ On the complexity of finding a Caristi's fixed point ⋮ Unique End of Potential Line ⋮ The Hairy Ball Problem is PPAD-Complete. ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ 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

• Exponential lower bounds for finding Brouwer fixed points
• On the complexity of the parity argument and other inefficient proofs of existence
• A Sperner lemma complete for PPA
• The complexity of computing a Nash equilibrium
• Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
• On algorithms for discrete and approximate brouwer fixed points
• Fundamentals of Computation Theory