The search complexity classes PPA and PPAD were proposed by Papadimitriou twenty years ago for characterizing the computational difficulties of many interesting natural search problems. While many members in the complete class of PPAD, PPAD-complete, are established in the past twenty years, the understanding of the PPA-complete class falls far behind.
We consider the problem of finding a fully colored base triangle on the 2-dimensional M\"obius band under the standard boundary condition, proving it to be PPA-complete. It completes the locally planar PPA-complete characterization approach known ten years ago for less natural non-orientable surfaces. Our 2D simple M\"obius band PPA-complete work establishes an eternal result in that direction.
The proof is based on a construction for the DPZP problem, that of finding a zero point under a discrete version of continuity condition. It further derives PPA-complete for versions on the M\"obius band of the following problems: the Sperner problem; the Tucker problem, finding an edge such that if the value of one end vertex is $x$, the other is $-x$, given an appropriate boundary condition.
More generally, this applies to other non-orientable spaces. We derive a variety of the other models, including the projective plane and the Klein bottle. However, since those models have a closed boundary, we rely on a version of the PPA that states it as to find another fixed point giving a fixed point. This model also makes it presentationally simple for an extension to a high dimensional discrete fixed point problem on a non-orientable (nearly) hyper-grid with a constant side length.
The search complexity classes {\bf PPA} and {\bf PPAD} were proposed by Papadimitriou twenty years ago for characterizing the computational difficulties of many interesting natural search problems. While many members in the complete class of {\bf PPAD}, {\bf PPAD}-completeness, are established in the past twenty years, the understanding of the {\bf PPA}-completeness class falls far behind.
We consider the problem of finding a fully colored base triangle on the $2$-dimensional M\"obius band under the standard boundary condition, proving it to be {\bf PPA}-complete. It completes the locally planar {\bf PPA}-complete characterization approach known ten years ago for less natural non-orientable surfaces. Our $2$D simple M\"obius band {\bf PPA}-complete work establishes an eternal result in that direction.
The proof is based on a construction for the DPZP problem, that of finding a zero point under a discrete version of continuity condition. It further derives {\bf PPA}-complete for versions on the M\"obius band of the following problems: the {\sc Sperner} problem; the {\sc Tucker} problem, finding an edge such that if the value of one end vertex is $x$, the other is $-x$, given an appropriate boundary condition. In addition, the construction allows for an extension to a high dimensional discrete fixed point problem on a non-orientable (nearly) hyper-grid with a constant side length.
