EUVIMEDEUVIMED entdecken
Crossref

Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →