Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)
SIAM Journal on Computing · 30.06.2024 · 53 (3) · 573-587
DOI: 10.1137/22m1498346 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 02.05.2024. Verfasst von Mika Göös und 6 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 23 Literaturangaben.
Abstract (Originalsprache)
We show [Formula: see text]. Here the class [Formula: see text] consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubáček and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse [Formula: see text] by Fearnley et al. (STOC 2021). We also prove a companion result [Formula: see text], where [Formula: see text] is the class associated with the Sink-of-Potential-Line problem.
Zitieren
APA
Göös, M., Hollender, A., Jain, S., Maystre, G., Pires, W., Robere, R., & Tao, R. (2024). Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\). SIAM Journal on Computing, 53(3), 573-587. https://doi.org/10.1137/22m1498346
Vancouver
Göös M, Hollender A, Jain S, Maystre G, Pires W, Robere R, et al. Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\). SIAM Journal on Computing. 2024;53(3):573-587. doi:10.1137/22m1498346
BibTeX
@article{Gs2024,
author = {Göös, Mika and Hollender, Alexandros and Jain, Siddhartha and Maystre, Gilbert and Pires, William and Robere, Robert and Tao, Ran},
title = {Further Collapses in \(\boldsymbol\mathsfTFNP\)},
journal = {SIAM Journal on Computing},
year = {2024},
volume = {53},
number = {3},
pages = {573--587},
doi = {10.1137/22m1498346}
}
EUVIMED