Corrigendum: PLS is contained in PLC
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910328266162176 |
|---|---|
| author | Ishizuka, Takashi |
| author_facet | Ishizuka, Takashi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_04051 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Corrigendum: PLS is contained in PLC Ishizuka, Takashi Computational Complexity 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. |
| title | Corrigendum: PLS is contained in PLC |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2312.04051 |