Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-002 | 7th February 2024 11:29

Corrigendum: PLS is contained in PLC

RSS-Feed




Revision #1
Authors: Takashi Ishizuka
Accepted on: 7th February 2024 11:29
Downloads: 127
Keywords: 


Abstract:

Recently, Pasarkar, Papadimitriou, and Yannakakis (ITCS 2023) have introduced the new TFNP subclass called PLC that contains the class PPP; they also have proven that several search problems related to extremal combinatorial principles (e.g., Ramsey’s theorem and the Sunflower lemma) belong to PLC. This short paper shows that the class PLC also contains PLS, a complexity class for TFNP problems that can be solved by a local search method. However, it is still open whether PLC contains the class PPA.



Changes to previous version:

There is a significant error in the proof of Lemma 14.


Paper:

TR24-002 | 4th December 2023 02:37

PLS is contained in PLC





TR24-002
Authors: Takashi Ishizuka
Publication: 7th January 2024 16:54
Downloads: 271
Keywords: 


Abstract:

Recently, Pasarkar, Papadimitriou, and Yannakakis (ITCS 2023) have introduced the new TFNP subclass called PLC that contains the class PPP; they also have proven that several search problems related to extremal combinatorial principles (e.g., Ramsey’s theorem and the Sunflower lemma) belong to PLC. This short paper shows that the class PLC also contains PLS, a complexity class for TFNP problems that can be solved by a local search method. However, it is still open whether PLC contains the class PPA.



ISSN 1433-8092 | Imprint