TY - GEN
T1 - Understanding PPA-completeness
AU - Deng, Xiaotie
AU - Edmonds, Jack R.
AU - Feng, Zhe
AU - Liu, Zhengyang
AU - Qi, Qi
AU - Xu, Zeying
N1 - Publisher Copyright:
© Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi.
PY - 2016/5/1
Y1 - 2016/5/1
N2 - We consider the problem of finding a fully colored base triangle on the 2-dimensional Möbius band under the standard boundary condition, proving it to be PPA-complete. 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-completeness for versions on the Möbius band of other related discrete fixed point type problems, and a special version of the Tucker problem, finding an edge such that if the value of one end vertex is x, the other is -x, given a special anti-symmetry boundary condition. More generally, this applies to other non-orientable spaces, 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.
AB - We consider the problem of finding a fully colored base triangle on the 2-dimensional Möbius band under the standard boundary condition, proving it to be PPA-complete. 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-completeness for versions on the Möbius band of other related discrete fixed point type problems, and a special version of the Tucker problem, finding an edge such that if the value of one end vertex is x, the other is -x, given a special anti-symmetry boundary condition. More generally, this applies to other non-orientable spaces, 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.
KW - Fixed point computation
KW - PPA-completeness
UR - http://www.scopus.com/inward/record.url?scp=84973358724&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CCC.2016.23
DO - 10.4230/LIPIcs.CCC.2016.23
M3 - Conference contribution
AN - SCOPUS:84973358724
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 23:1-23:25
BT - 31st Conference on Computational Complexity, CCC 2016
A2 - Raz, Ran
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 31st Conference on Computational Complexity, CCC 2016
Y2 - 29 May 2016 through 1 June 2016
ER -