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

^*此作品的通讯作者

科研成果: 期刊稿件 › 文章 › 同行评审

4 引用（Scopus）

摘要

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.

源语言	英语
页（从-至）	146-168
页数	23
期刊	Journal of Computer and System Sciences
卷	115
DOI	https://doi.org/10.1016/j.jcss.2020.07.006
出版状态	已出版 - 2月 2021
已对外发布	是

访问文件

10.1016/j.jcss.2020.07.006

其它文件与链接

链接到 Scopus 的出版物

引用此

@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

摘要

访问文件

其它文件与链接

指纹

引用此