4
[2202.07761] Further Collapses in TFNP
source link: https://arxiv.org/abs/2202.07761
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 15 Feb 2022 (v1), last revised 20 May 2022 (this version, v2)]
Further Collapses in TFNP
We show EOPL=PLS∩PPAD. Here the class EOPL consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubacek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse CLS=PLS∩PPAD by Fearnley et al. (STOC 2021). We also prove a companion result SOPL=PLS∩PPADS, where SOPL is the class associated with the Sink-of-Potential-Line problem.
| Subjects: | Computational Complexity (cs.CC) |
| Cite as: | arXiv:2202.07761 [cs.CC] |
| (or arXiv:2202.07761v2 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2202.07761 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK