Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-120 | 29th August 2015 08:17

Understanding PPA-Completeness

RSS-Feed




Revision #1
Authors: Xiaotie Deng, Jack Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, Zeying Xu
Accepted on: 29th August 2015 08:17
Downloads: 568
Keywords: 


Abstract:

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.


Paper:

TR15-120 | 12th July 2015 14:47

Understanding PPA-Completeness





TR15-120
Authors: Xiaotie Deng, Zhe Feng, Zhengyang Liu, Qi Qi
Publication: 24th July 2015 15:44
Downloads: 727
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint