Further collapses in TFNP
Further collapses in TFNP
复制标题
TFNP进一步崩溃
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ran Tao
中科院分区：
文献类型：
--
作者：
Mika Goos;Alexandros Hollender;Siddhartha Jain;Gilbert Maystre;William Pires;Robert Robere;Ran Tao
我们证明EOPL = PLS PPAD。在这里，EOPL类由所有的总搜索问题组成，这些问题可以简化为电位线末端问题，这是Hubáček和Yogev（SICOMP 2020）和Fearnley等人（JCSS 2020）在工作中引入的。特别是，我们的结果产生了Fearnley等人（STOC 2021）的突破崩溃CLS = PLS PPAD的新的更简单的证明。我们还证明了一个同伴的结果SOPL = PLS <$PPADS，其中SOPL是与潜在的线汇问题的类。
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 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 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.
塔斯基定理、超模博弈和均衡的复杂性
DOI：
10.4230/lipics.itcs.2020.18
发表时间：
2020
期刊：
11th Innovations in Theoretical Computer Science Conference
影响因子：
--
作者：
Etessami, Kousha;Papadimitriou, Christos H;Rubinstein, Aviad;Yannakakis, Mihalis
通讯作者：
Yannakakis, Mihalis
势线的独特末端
影响因子：
--
作者：
Fearnley, John;Gordon, Spencer;Mehta, Ruta;Savani, Rahul
通讯作者：
Savani, Rahul
线尾的彩虹 - 彩色卡拉西奥多里定理的 PPAD 公式及其应用
DOI：
10.1137/1.9781611974782.87
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
Meunier;Frédéric;Mulzer;Wolfgang;Sarrabezolles;Pauline;Yannik
通讯作者：
Yannik