On the Complexity of 2D Discrete Fixed Point Problem

DOI10.1007/11786986_43zbMath1223.68054OpenAlexW2584543285MaRDI QIDQ3613784

Xi Chen, Xiaotie Deng

Publication date: 12 March 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11786986_43

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (9)

A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium ⋮ On the black-box complexity of Sperner's Lemma ⋮ Constant Rank Two-Player Games are PPAD-hard ⋮ \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma ⋮ Colorful linear programming, Nash equilibrium, and pivots ⋮ Recent development in computational complexity characterization of Nash equilibrium ⋮ Quantum and classical query complexities of local search are polynomially related ⋮ 2-D Tucker is PPA complete ⋮ A simplicial approach for discrete fixed point theorems

This page was built for publication: On the Complexity of 2D Discrete Fixed Point Problem