Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2412.03395 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910728055685120 |
|---|---|
| author | Darmann, Andreas Döcker, Janosch Dorn, Britta |
| author_facet | Darmann, Andreas Döcker, Janosch Dorn, Britta |
| contents | We show that Not-All-Equal 3-Sat remains NP-complete when restricted to instances that simultaneously satisfy the following properties: (i) The clauses are given as the disjoint union of k partitions, for any fixed $k \geq 4$, of the variable set into subsets of size 3, and (ii) each pair of distinct clauses shares at most one variable. Property (i) implies that each variable appears in exactly $k$ clauses and each clause consists of exactly 3 unnegated variables. Therewith, we improve upon our earlier result (Darmann and Döcker, 2020). Complementing the hardness result for at least $4$ partitions, we show that for $k\leq 3$ the corresponding decision problem is in P. In particular, for $k\in \{1,2\}$, all instances that satisfy Property (i) are nae-satisfiable.
By the well-known correspondence between Not-All-Equal 3-Sat and hypergraph coloring, we obtain the following corollary of our results: For $k\geq 4$, Bicolorability is NP-complete for linear 3-uniform $k$-regular hypergraphs even if the edges are given as a decomposition into $k$ perfect matchings; with the same restrictions, for $k \leq 3$ Bicolorability is in P, and for $k \in \{1,2\}$ all such hypergraphs are bicolorable.
Finally, we deduce from a construction in the work by Pilz (Pilz, 2019) that every instance of Positive Planar Not-All-Equal Sat with at least three distinct variables per clause is nae-satisfiable. Hence, when restricted to instances with a planar incidence graph, each of the above variants of Not-All-Equal 3-Sat turns into a trivial decision problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_03395 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An even simpler hard variant of Not-All-Equal 3-SAT Darmann, Andreas Döcker, Janosch Dorn, Britta Computational Complexity We show that Not-All-Equal 3-Sat remains NP-complete when restricted to instances that simultaneously satisfy the following properties: (i) The clauses are given as the disjoint union of k partitions, for any fixed $k \geq 4$, of the variable set into subsets of size 3, and (ii) each pair of distinct clauses shares at most one variable. Property (i) implies that each variable appears in exactly $k$ clauses and each clause consists of exactly 3 unnegated variables. Therewith, we improve upon our earlier result (Darmann and Döcker, 2020). Complementing the hardness result for at least $4$ partitions, we show that for $k\leq 3$ the corresponding decision problem is in P. In particular, for $k\in \{1,2\}$, all instances that satisfy Property (i) are nae-satisfiable. By the well-known correspondence between Not-All-Equal 3-Sat and hypergraph coloring, we obtain the following corollary of our results: For $k\geq 4$, Bicolorability is NP-complete for linear 3-uniform $k$-regular hypergraphs even if the edges are given as a decomposition into $k$ perfect matchings; with the same restrictions, for $k \leq 3$ Bicolorability is in P, and for $k \in \{1,2\}$ all such hypergraphs are bicolorable. Finally, we deduce from a construction in the work by Pilz (Pilz, 2019) that every instance of Positive Planar Not-All-Equal Sat with at least three distinct variables per clause is nae-satisfiable. Hence, when restricted to instances with a planar incidence graph, each of the above variants of Not-All-Equal 3-Sat turns into a trivial decision problem. |
| title | An even simpler hard variant of Not-All-Equal 3-SAT |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2412.03395 |