论文标题
TFNP进一步崩溃
Further Collapses in TFNP
论文作者
论文摘要
我们显示$ \ textsf {eopl} = \ textsf {pls} \ cap \ textsf {ppad} $。在这里，$ \ textsf {eopl} $由所有总搜索问题组成，这些问题减少到了潜在的线问题，这是Hubacek和Yogev（Sicomp 2020）和Fearnley等人在作品中引入的。 （JCSS 2020）。特别是，我们的结果产生了突破性崩溃$ \ textsf {cls} = \ textsf {pls} \ cap \ textsf {ppad} $的新简单证明。 （STOC 2021）。我们还证明了一个伴随结果$ \ textsf {sopl} = \ textsf {pls} \ cap \ cap \ textsf {ppads} $，其中$ \ textsf {sopl} $是与接收器线的类问题关联的类。
We show $\textsf{EOPL}=\textsf{PLS}\cap\textsf{PPAD}$. Here the class $\textsf{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 $\textsf{CLS}=\textsf{PLS}\cap\textsf{PPAD}$ by Fearnley et al. (STOC 2021). We also prove a companion result $\textsf{SOPL}=\textsf{PLS}\cap\textsf{PPADS}$, where $\textsf{SOPL}$ is the class associated with the Sink-of-Potential-Line problem.
