MCQ:

The NOT-ALL-EQUAL 3SAT problem is defined as follows: Given a 3-CNF formula F, is there a truth assignment for the variables such that each clause has at least one true literal and at least one false literal? The NOT-ALL-EQUAL 3SAT problem is NP-complete.

This question is about trying to reduce the NOT-ALL-EQUAL 3SAT problem to the MAX-CUT problem defined below to show the latter to be NP-complete.

A cut in an undirected graph G=(V,E) is a partitioning of the set of nodes V into two disjoint subsets V1 and V2. The size of a cut is the number of edges e = (u,v) where u is in V1 and v is in V2. The MAX-CUT problem is defined as follows: Given an undirected graph G=(V,E) and a positive integer k, does G have a cut of size k or more?

Given a 3CNF expression E, we create the graph G = (V,E). Then given an assignment A, create a cut C in G by partitioning the set of nodes V as follows: the nodes corresponding to the uncomplemented literals are in set V1 and those corresponding to the complemented variables are in set V2.

For variable a, let a' denote NOT(a). Let

E = (a + b + c)(a + b' + c)(a' + b' + d)(c' + d' + e)

be an instance of NOT-ALL-EQUAL 3SAT. Suppose a cut separates the true nodes from false nodes according to some truth assignment applied to E. How many edges between nodes corresponding to the literals in the same clause are cut? How many other edges are cut? Find out how the cut-size can be computed for an arbitrary instance of NOT-All-EQUAL 3SAT. Then for the instance E, determine in which of the cases below, the cut-size C corresponds to the satisfiable assignment given.

a) a = T, b = T, c = F, d = F, e = T, C = 13

b) a = T, b = T, c = T, d = T, e = T, C = 15

c) a = T, b = F, c = F, d = T, e = F, C = 15

d) a = T, b = F, c = F, d = T, e = F, C = 8