Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-037 | 10th February 2006 00:00

On the Complexity of 2D Discrete Fixed Point Problem

RSS-Feed




TR06-037
Authors: Xi Chen, Xiaotie Deng
Publication: 17th March 2006 05:21
Downloads: 3960
Keywords: 


Abstract:

While the 3-dimensional analogue of the Sperner problem in the plane was known to be PPAD-complete, the complexity of the 2D-SPERNER itself is not known to be PPAD-complete or not. In this paper, we settle this open problem proposed by Papadimitriou~\cite{PAP90} fifteen years ago. This also allows us to derive the computational complexity characterization of a discrete version of the 2-dimensional Brouwer fixed point problem, improving a recent result of Daskalakis, Goldberg and Papadimitriou~\cite{DAS05}. Those results will be very useful tools to the study of other related problems.



ISSN 1433-8092 | Imprint