Not-all-equal 3-satisfiability

In computational complexity, not-all-equal 3-satisfiability (NAE3SAT) is an NP-complete variant of the Boolean satisfiability problem, often used in proofs of NP-completeness.[1]

Definition

Like 3-satisfiability, an instance of the problem consists of a collection of Boolean variables and a collection of clauses, each of which combines three variables or negations of variables. However, unlike 3-satisfiability, which requires each clause to have at least one true Boolean value, NAE3SAT requires that the three values in each clause are not all equal to each other (in other words, at least one is true, and at least one is false).[2]

Hardness

The NP-completeness of NAE3SAT can be proven by a reduction from 3-satisfiability.[2]

The problem remains NP-complete when all clauses are monotone (meaning that variables are never negated), by Schaefer's dichotomy theorem.[3] Monotone NAE3SAT can also be interpreted as an instance of the set splitting problem, or as a generalization of graph bipartiteness testing to 3-uniform hypergraphs: it asks whether the vertices of a hypergraph can be colored with two colors so that no hyperedge is monochromatic. More strongly, it is NP-hard to find colorings of 3-uniform hypergraphs with any constant number of colors, even when a 2-coloring exists.[4]

Easy cases

Unlike 3SAT, some variants of NAE3SAT in which graphs representing the structure of variables and clauses are planar graphs can be solved in polynomial time. In particular this is true when there exists a planar graph with one vertex per variable, one vertex per clause, an edge for each variable-clause incidence, and a cycle of edges connecting all the variable vertices.[5]

gollark: One thing I want to do at some point is train a LLM on large amounts of message logs and interface it with one of the *several* developed ways to sort of kind of give them longer-term memory.
gollark: Paste in the article on apioforms and my latest video and such.
gollark: Just try it with few-shot prompting.
gollark: Just use the gollarious synthesizer program™.
gollark: That's not *my* bismuth.

References
  1. Moret (1988): "Among published proofs of NP-completeness, one finds more reductions from 3-Satisfiability (3SAT for short) and its main variants, One- in-three-3SAT (1in3SAT) and Not-all-equal 3SAT (NAE3SAT), than from any other NP-complete problem."
  2. Moore, Cristopher; Mertens, Stephan (2011), "Symmetry-breaking and NAESAT", The Nature of Computation, Oxford University Press, pp. 133–138, ISBN 9780199233212
  3. Schaefer, Thomas J. (1978), "The complexity of satisfiability problems", Proc. Tenth ACM Symposium on Theory of Computing (STOC '78), New York: ACM, pp. 216–226, MR 0521057
  4. Dinur, Irit; Regev, Oded; Smyth, Clifford (2005), "The hardness of 3-uniform hypergraph coloring", Combinatorica, 25 (5): 519–535, doi:10.1007/s00493-005-0032-4, MR 2176423
  5. Moret, B. M. E. (June 1988), "Planar NAE3SAT is in P", ACM SIGACT News, 19 (2): 51–54, doi:10.1145/49097.49099
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.