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.