We show EOPL = PLS \cap PsansP \sansP AD. 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'acv \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 \cap PsansP \sansP AD by Fearnley et al. (STOC 2021). We also prove a companion result SOPL = PLS \cap PsansP \sansP ADS, where SOPL is the class associated with the SINK -OF -POTENTIAL -LINE problem.
Gilbert Théodore Maystre, Ran Tao, Mika Tapani Göös, Siddhartha Jain, Alexandros Paul Hollender
Rico Zenklusen, Ola Nils Anders Svensson, Ashkan Norouzi Fard, Moran Feldman
Volkan Cevher, Ilija Bogunovic, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakub Tarnawski