2026-08-11T23:13:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5831 2024-03-06T10:37:11Z ddc:004 open_access

Understanding PPA-Completeness Deng, Xiaotie Edmonds, Jack R. Feng, Zhe Liu, Zhengyang Qi, Qi Xu, Zeying Fixed Point Computation PPA-Completeness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiaotie Deng and Jack R. Edmonds and Zhe Feng and Zhengyang Liu and Qi Qi and Zeying Xu 2016 Is Part Of LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2016.23 urn:nbn:de:0030-drops-58310 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.23 eng https://creativecommons.org/licenses/by/3.0/legalcode