We’re starting a new section and a lot of the introductory problems have been covered elsewhere.

LO1 is Satisfiability

LO2 is 3-Satisfiability

LO3 is Not all Equal 3SAT

LO4 is One-In-Three 3SAT

LO5 is Maximum 2SAT

After that we finally get to a new problem:

**The Problem: **Generalized Satisfiability. This is problem LO6 in the appendix.

**The description: **Given a list of positive integers k_{1} through k_{m} and a sequence S = <R_{1}..R_{m}>, where each R_{i }is a set of strings of k_{i} “T” or “F” symbols. We’re also given a set U of variables, and a set of collections C_{1} through C_{m}. Each C_{i} contains a k_{i}-tuple of variables from U.

Can we assign a truth value (“T” or “F”) to each variable in U such that for each tuple in C_{i} the truth value of each variable in the tuple matches the sequence of true and false values in R_{i}?

**Example: **Let all k_{i} = 3, and m = 2. R1 = {(T,T,T), (F,F,F)} R2 = {(T,F,F). (F,T,T)}

U = {x_{1}, x_{2}, x_{3}}. C1 = (x_{1}, x_{2}, x_{3}}. C_{2} = {x_{1}, x_{2}, x_{3}}

So, the question is: Can we assign truth values to x_{1} x_{2} and x_{3} so that the truth values map to a sequence in both R0 and R1? Since we have the same sequences of the same variables in both sets, the answer is no.

But, suppose we change C_{2} to (x_{4}, x_{2}, x_{3}). Then we can set x_{1}, x_{2}, and x_{3} to true and x_{4} to false. This will let the sequence in C_{1} map to the (T,T,T) sequence in R1, and the sequence in C_{2} map to the (F,T,T) sequence in R2.

**Reduction: **This reduction is in Shaefer’s paper, and it reduces from 3SAT. The idea is that we will build 4 R sets, thinking of them as functions. So:

R0 = {R(x,y,z) | x or y or z is true} = {(T,T,T), (T,T,F), (T,F,T), (T,F,F), (F,T,T), (F,T,F), (F,F,T)}

R1 =Same idea, but “~x or y or z is true”

R2 = “~x or ~y or z is true”

R3 = ” ~x or ~y or ~z is true”

Once we’re given a CNF instance, we replace each clause in the formula with one of the Ri formulas. Then build a C set that uses the variables in the clause. So, for example, if a clause in the CNF formula was ~x_{2} ∨ x_{5} ∨ ~x_{7}, we’d make the element in R corresponding to the clause R2, and we’d use the C formula (x_{2}, x_{7}, x_{5}). Notice that we changed the order of the variables in the C set because R2 expects its negated literals first.

Notice that we can find a way to assign the variables truth values to make each C_{i} map to its R set, we have satisfied the clause. So this new construction is satisfiable if and only if the 3SATinstance was satisfiable.

**Difficulty: **Making the construction is probably a 5, mostly because you need a good way to explain how you’re making the R sets. The hardest thing here though is understanding what the problem says.