Understanding PPA-completeness

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

doi:10.1016/j.jcss.2020.07.006

Understanding PPA-completeness

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

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

We show that computation of the SPERNER problem is PPA-complete on the Möbius band under proper boundary conditions, settling a long term open problem. Further, the same computational complexity results extend to other discrete fixed points on the Möbius band, such as the Brouwer fixed point problem, the DPZP fixed point problem and a simple version of the Tucker problem, as well as the projective plane and the Klein bottle. We expect it opens up a new route for further studies on the related combinatorial structures.

Original language	English
Pages (from-to)	146-168
Number of pages	23
Journal	Journal of Computer and System Sciences
Volume	115
DOIs	https://doi.org/10.1016/j.jcss.2020.07.006
Publication status	Published - Feb 2021
Externally published	Yes

Keywords

Fixed point computation
Oracle model complexity
PPA-completeness

Access to Document

10.1016/j.jcss.2020.07.006

Cite this

@article{9a4bf542a01d446ca52c1d29906e4ec6,

title = "Understanding PPA-completeness",

abstract = "We show that computation of the SPERNER problem is PPA-complete on the M{\"o}bius band under proper boundary conditions, settling a long term open problem. Further, the same computational complexity results extend to other discrete fixed points on the M{\"o}bius band, such as the Brouwer fixed point problem, the DPZP fixed point problem and a simple version of the Tucker problem, as well as the projective plane and the Klein bottle. We expect it opens up a new route for further studies on the related combinatorial structures.",

keywords = "Fixed point computation, Oracle model complexity, PPA-completeness",

author = "Xiaotie Deng and Edmonds, {Jack R.} and Zhe Feng and Zhengyang Liu and Qi Qi and Zeying Xu",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

year = "2021",

month = feb,

doi = "10.1016/j.jcss.2020.07.006",

language = "English",

volume = "115",

pages = "146--168",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Understanding PPA-completeness

AU - Deng, Xiaotie

AU - Edmonds, Jack R.

AU - Feng, Zhe

AU - Liu, Zhengyang

AU - Qi, Qi

AU - Xu, Zeying

PY - 2021/2

Y1 - 2021/2

N2 - We show that computation of the SPERNER problem is PPA-complete on the Möbius band under proper boundary conditions, settling a long term open problem. Further, the same computational complexity results extend to other discrete fixed points on the Möbius band, such as the Brouwer fixed point problem, the DPZP fixed point problem and a simple version of the Tucker problem, as well as the projective plane and the Klein bottle. We expect it opens up a new route for further studies on the related combinatorial structures.

AB - We show that computation of the SPERNER problem is PPA-complete on the Möbius band under proper boundary conditions, settling a long term open problem. Further, the same computational complexity results extend to other discrete fixed points on the Möbius band, such as the Brouwer fixed point problem, the DPZP fixed point problem and a simple version of the Tucker problem, as well as the projective plane and the Klein bottle. We expect it opens up a new route for further studies on the related combinatorial structures.

KW - Fixed point computation

KW - Oracle model complexity

KW - PPA-completeness

UR - http://www.scopus.com/inward/record.url?scp=85089508656&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2020.07.006

DO - 10.1016/j.jcss.2020.07.006

M3 - Article

AN - SCOPUS:85089508656

SN - 0022-0000

VL - 115

SP - 146

EP - 168

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -

Understanding PPA-completeness

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this