1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915276404031488 |
|---|---|
| author | Ciardo, Lorenzo Kozik, Marcin Krokhin, Andrei Nakajima, Tamio-Vesa Živný, Stanislav |
| author_facet | Ciardo, Lorenzo Kozik, Marcin Krokhin, Andrei Nakajima, Tamio-Vesa Živný, Stanislav |
| contents | The 1-in-3 and Not-All-Equal satisfiability problems for Boolean CNF formulas are two well-known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Equal problem can be solved in polynomial time. In the present work, we investigate this constraint satisfaction problem in a regime where the promise is weakened from either side by a rainbow-free structure, and establish a complexity dichotomy for the resulting class of computational problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_03456 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise Ciardo, Lorenzo Kozik, Marcin Krokhin, Andrei Nakajima, Tamio-Vesa Živný, Stanislav Computational Complexity Discrete Mathematics Data Structures and Algorithms The 1-in-3 and Not-All-Equal satisfiability problems for Boolean CNF formulas are two well-known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Equal problem can be solved in polynomial time. In the present work, we investigate this constraint satisfaction problem in a regime where the promise is weakened from either side by a rainbow-free structure, and establish a complexity dichotomy for the resulting class of computational problems. |
| title | 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2302.03456 |