Understanding PPA-completeness

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

科研成果: 书/报告/会议事项章节会议稿件同行评审

10 引用 (Scopus)

摘要

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.

源语言英语
主期刊名31st Conference on Computational Complexity, CCC 2016
编辑Ran Raz
出版商Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
23:1-23:25
ISBN(电子版)9783959770088
DOI
出版状态已出版 - 1 5月 2016
已对外发布
活动31st Conference on Computational Complexity, CCC 2016 - Tokyo, 日本
期限: 29 5月 20161 6月 2016

出版系列

姓名Leibniz International Proceedings in Informatics, LIPIcs
50
ISSN(印刷版)1868-8969

会议

会议31st Conference on Computational Complexity, CCC 2016
国家/地区日本
Tokyo
时期29/05/161/06/16

指纹

探究 'Understanding PPA-completeness' 的科研主题。它们共同构成独一无二的指纹。

引用此