On the complexity of 2D discrete fixed point problem
From MaRDI portal
Publication:1035680
DOI10.1016/j.tcs.2009.07.052zbMath1183.68294OpenAlexW1826384874MaRDI QIDQ1035680
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
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