Understanding PPA-completeness

Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, Zeying Xu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication31st Conference on Computational Complexity, CCC 2016
EditorsRan Raz
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages23:1-23:25
ISBN (Electronic)9783959770088
DOIs
Publication statusPublished - 1 May 2016
Externally publishedYes
Event31st Conference on Computational Complexity, CCC 2016 - Tokyo, Japan
Duration: 29 May 20161 Jun 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume50
ISSN (Print)1868-8969

Conference

Conference31st Conference on Computational Complexity, CCC 2016
Country/TerritoryJapan
CityTokyo
Period29/05/161/06/16

Keywords

  • Fixed point computation
  • PPA-completeness

Fingerprint

Dive into the research topics of 'Understanding PPA-completeness'. Together they form a unique fingerprint.

Cite this