Olga Zverovich, ‘10

Harvard University, Department of Mathematics

“Does P=NP?” is one of the biggest open questions in theoretical computer science. An important advance toward answering this question came in 1971, when Stephen Cook proved that a problem in NP—the Satisfiability Problem, or simply SAT—has the property that if this problem is “easy” (polynomial-time solvable), then all problems in NP are easy.  Such problems are called NP-complete.  As the first NP-complete problem, SAT has great theoretical and practical significance. The Minimum Assignment Problem is a generalization of SAT that asks about the existence of satisfying partial assignments to Boolean formulae.  It is shown that the Minimum Assignment Problem is NP-complete for 2-CNF and Horn CNF formulae, two well-known classes of formulae where SAT is easy. The central finding is that the Minimum Assignment Problem is easy for “directed” 2-CNFs, a class of formulae in the intersection of 2-CNFs and Horn CNFs. Finally, the Minimum Assignment Problem for Boolean polynomials is investigated.  The satisfiability/unsatisfiability problems are easy for Boolean polynomials. Two generalizations are introduced—the Minimum True Assignment Problem and the Minimum False Assignment Problem for polynomials—and it is shown that while the problems are easy for linear polynomials, they are NP-complete for quadratic polynomials. A key result is that both problems are easy for bilinear polynomials (quadratic polynomials represented as a product of two linear polynomials).

Introduction

In this paper, we introduce the Minimum Assignment Problem—a generalization of the famous Satisfiability Problem. The Minimum Assignment Problem asks about the existence of satisfying partial assignments to Boolean formulae. We exhibit an interesting class for which the problem is tractable—“directed” 2-CNFs.

We consider the Satisfiability Problem. Let X = (x1, x2, ,xn) be an ordered set of 0–1 variables. A literal over X is either a variable x X [positive literal] or its negation (x-bar)i = 1 – xi [negative literal]. Denote the set of literals over X by LX. A truth assignment to X is a point xo = (x1o, x2o,…, xno)of the n-dimensional Boolean cube B n = {0,1}n

A Boolean function is a mapping ƒ: Bn →B. There are three main representations of an arbitrary Boolean function ƒ over X:

conjunctive normal form [CNF]: C = C1C2…Cm where each clause Ci is disjunction of some literals of X (and CiCj is the conjuction of Ci and Cj),

disjunctive normal form [DNF]: D = T1 T2 ∨. . .∨ Tm where each term Ti is conjunction of some literals of X, and

Boolean polynomial: P = T1 T2 ⊕ . . . ⊕ Tm where each term Ti is product of some variables of X, and ⊕ denotes mod 2 addition.

A truth assignment xo satisfies a Boolean formula f if f(xo) = 1.

Decision Problem 1 (SAT)
Instance: A CNF C over X.
Question: Is there a truth assignment to X that satisfies C?

Cook proved that SAT is an NP-complete problem. (Note that the similar Unsatisfiability Problem is trivial for CNFs. Indeed, we can pick any clause and assign any values to the variables in that clause. If the clause evaluates to 1, we simply change the value of one of the variables. Thus, each CNF takes on value 0 at some point.) If each clause in C involves at most k literals for some integer k, i.e., C is a kCNF, then SAT is called the kSAT Problem. It is well-known that k-SAT is an NP-complete problem for each k ≥ 3, while 2-SAT can be solved in linear time, see Garey and Johnson .

In Section 2, we consider a natural generalization of the SAT Problem called the Minimum Assignment Problem. Given a CNF C and an integer k, we ask whether there is a an assignment xo of Boolean values to at most k of the variables that satisfies C, in the sense that C(xo) evaluates to 1 for every assignment of values to the undenied variables. It is interesting to find classes of Boolean formulae for which this problem is polynomial-time solvable. We observe that the Minimum Assignment Problem problem is NP-complete even for 2-CNFs, but we propose a non-trivial polynomial-time solvable case, namely “directed” 2-CNFs. As a byproduct, we prove that a variant of the Vertex Cover Problem for directed graphs can be solved in polynomial time. This may be surprising in light of the fact that the Vertex Cover Problem for undirected graphs is NP-complete.

In section 3, we investigate the Minimum Assignment Problem for Boolean polynomials. Both, the Satisability Problem and the Unsatisfiability Problem are easy (polynomial-time solvable) for Boolean polynomials. As we will see, this follows from the fact that every Boolean function can be represented uniquely as a Boolean polynomial. We introduce two generalizations—the Minimum True Assignment Problem and the Minimum False Assignment Problem for polynomials. We prove that both problems are NP-complete even for quadratic polynomials. However, the problems are easy for linear polynomials. Comparing these two results, we see that it is interesting to investigate the problems for an intermediate class of bilinear polynomials, quadratic polynomials representable as product of two linear polynomials. Our main result is that both the Minimum True Assignment Problem and the Minimum False Assignment Problem for bilinear polynomials can be solved eciently. The two problems are not similar within the class of bilinear polynomials: the algorithm for the Minimum False Assignment Problem is more complicated than that for the Minimum True Assignment Problem. We give solutions to the search versions of the decision problems. That is, we answer an existential question in a constructive way by producing a solution.

Partial assignments

Here we introduce a generalization of the Satisfiability Problem.

Definition 1
A partial assignment to X = (x1, x2, ,xn) is a point in the set {0, 1, ✴}n, where means that value of the corresponding variable is undetermined. The size of a partial assignment xo, size(xo), is defined as the total number of zeroes and ones in xo.

For example, (0, c, 1, ✴) is a partial assignment of size two to (x1, x2, x3, x4) with x1 = 0, x3 = 1, and with undefined values of x2 and x4. In general, if cjC is a clause and xo is a partial assignment to X, cj(xo) is a Boolean function, since the values of all variables xi of cj with xio = ✴ are undefined. If cj(xo) evaluates to 1 for every assignment of the undefined variables, we say cj(xo) ≡1 and xo satisfies cj.

Decision Problem 2 (Minimum Assignment)
Instance: A CNF C over X and an integer k.
Question: Is there a partial assignment to X of size at most k that satisfies C?

The corresponding optimization problem is to find a minimum-size partial assignment to X that satisfies C, or to detect that there is no such an assignment. Consider, for example, the following CNF C = c1c2c3, where c1 = (x1 ∨ x2), c2 = (x1 x3), c3 = (x2 x3). If x1 = 1 then c1 is satisfied, x3 = 1 [to satisfy c2], and c3 is satisfied by x3. We obtain a partial assignment (1, ✴, 1) of size 2 satisfying C. Setting x1 = 0, we obtain (0, 0, 1), a partial assignment of size 3. Finally, if x1 = ✴ then we have a partial assignment (✴, 0, 1) of size 2 satisfying C. First we show that the Minimum Assignment Problem is hard even for 2-CNFs.

Proposition 1. The Minimum Assignment Problem is NP-complete even if each clause has exactly two literals, both of which are positive.

Proof. First, the Minimum Assignment Problem for 2-CNFs is in NP. Indeed, since 2-SAT is solvable in polynomial time (even in its search version), we can check in polynomial time whether a given partial assignment satisfies a 2-CNF (and is of the right size).

Next, we construct a polynomial-time reduction from the Vertex Cover Problem which is known to be NP-hard. A vertex cover in a graph G with vertex set V is a vertex subset T V such that each edge of G has at least one of its ends in T. Equivalently, S = V \ T is a independent set; that is, no edge of G has both of its ends in S.

Decision Problem 3 (Vertex Cover)
Instance: A graph G and an integer k.
Question: Does G have a vertex cover T with |T| ≤ k?

Given an instance (G, k) to the Vertex Cover Problem, we consider vertex-set X of G as a set of Boolean variables. Further, we define a 2-CNF C = {ce : eE} over X by the following: ce = (xi xj) for each edge e = xi xj of G.

If T is a vertex cover in G with |T| ≤ k, then C is satisfied by the following partial assignment xT of size |T|: = 1 if xiT, and = ✴ otherwise.

Conversely, let xo be a partial assignment of size at most k satisfying C. The vertices corresponding to ones of xo constitute a vertex cover To in G with |To| ≤ k.

A Horn clause is a clause that contains at most one negative literal. Accordingly, a Horn CNF consists of Horn clauses only. The corresponding Satisfiability Problem, Horn SAT, can be solved in polynomial time, see for example Dowling and Gallier . Proposition 1 shows that the Minimum Assignment Problem is NP-complete for Horn CNFs. Now we define an interesting class of CNFs for which the problem is tractable.

Definition 2. A directed 2-CNF is a 2-CNF C such that each clause in C has exactly one positive literal and exactly one negative literal.

Our main result in this section is

Theorem 1. The Minimum Assignment Problem for directed 2-CNFs can be solved in polynomial time.

First, we observe that there is a natural one-to-one correspondence between directed 2-CNFs and digraphs. This correspondence will enable us to formulate the Minimum Assignment Problem for directed 2-CNFs as a problem in graph theory.

Given a directed 2-CNF C over X, we can construct a digraph DC = (X, A) as follows: there exists an arc (xi, xj) in DC if and only if (xi xj) ∈ C. Conversely, given a digraph (X, A), we can construct the corresponding 2-CNF over X. We use notation V(D) and A(D) for vertex-set and arc-set of a digraph D, respectively.

We now define a notion of a vertex cover for digraphs.

Definition 3. A directed vertex cover in a digraph D is an ordered pair (T, F) of disjoint subsets T,F V(D) such that, for each arc (u, v) A(D), either

(DIV1): uT, or

(DIV2): vF.

The size of a directed vertex cover (T, F) is defined as size(T, F) = |T| + |F|.

Decision Problem 4 (Directed Vertex Cover)
Instance: A digraph D and an integer k.
Question: Does D have a directed vertex cover (T, F) with size(T, F) ≤ k?

We relate directed vertex covers to minimum assignments.

Proposition 2. The Minimum Assignment Problem for directed 2-CNFs and the Directed Vertex Cover Problem are polynomial-time equivalent.

Proof. Let a directed 2-CNF C and k be an instance to the Minimum Assignment Problem. We consider the corresponding digraph DC and k as an instance to the Directed Vertex Cover Problem.

Suppose that DC has a directed vertex cover (T, F) with size(T, F) k. Using T and F, we define a partial truth assignment xo to X by Clearly, size(xo) = size(T, F) ≤ k. We show that xo satisfies C. Indeed, let  be an arbitrary clause of C. Accordingly, (xi, xj) is an arc of the digraph DC. By Definition 3, either (DIV1) or (DIV2) holds for the arc (xi, xj). If (DIV1) holds then xi T, and therefore = 1, implying that xo satisfies C. If xj F [the condition (DIV2)], then = 0, and again xo satisfies C. Thus, Directed Vertex Cover is polynomial-time reducible to Minimum Assignment.

Conversely, suppose that there exists a partial assignment xo to X of size at most k that satisfies C. We define disjoint subsets T and F of V(DC) by T = {xi : xjo = 1} and F = {xi : xjo = 0}. It is easy to see that both (DIV1) and (DIV2) hold for (T, F). Hence (T, F) is a directed vertex cover of DC with size(T, F) = size(xo) k. Thus, the Minimum Assignment Problem is polynomial-time reducible to the Directed Vertex Cover Problem.

By Proposition 2, it suffices to prove that Directed Vertex Cover has a polynomial-time solution to establish Theorem 1. To accomplish this, we first reduce Directed Vertex Cover to a variant of the problem for acyclic digraphs, called the Restricted Directed Vertex Cover Problem. We begin with some definitions.

A digraph is called strongly connected if it contains a directed (u, v)-path for each ordered pair (u, v) of vertices. A strong component in a digraph D is an inclusion-wise maximal strongly connected subgraph of D. A strong component is trivial if it has exactly one vertex, and it is non-trivial otherwise. For a directed vertex cover of (T, F) of a digraph D, we define the rest of (T, F) as R = V(D) \ (TF).

The following lemma will be useful for our next important result.

Lemma 1. Let D be a digraph, and let (T, F) be a directed vertex cover in D. Let u T, v F be distinct vertices of D. Then, there is no (u, v)-directed path in D.

Proof. Suppose u T and there is a (u, v)-directed path P = (u = u1, u2, …, uk = v) in S. For the arc (u1, u2) the condition (DIV1) does not hold, therefore u2F according to (DIV2). Continuing inductively, we get ut F for each 2 t k. In particular, v F.

Proposition 3. Let (T, F) be a directed vertex cover in a digraph D, and let S be an arbitrary strong component of D. Then, S is entirely contained in one of T, F, and R. Furthermore, if S R, then |S| = 1.

Proof. Suppose that S has a vertex u S \ T and a vertex v S T. By Lemma 1, there is no (u, v)-directed path in S, a contradiction to the fact that S is strongly connected.

Suppose that S has a vertex u S F and a vertex v S \ F. By Lemma 1, there is no (u, v)-directed path in S, a contradiction.

If S R then either S T ≠ 0 [and therefore ST] or SF ≠ 0 [and hence SF]. In any case, S is disjoint from R.

If D has an arc (u, v) with u, v R, then we have a contradiction to both (DIV1) and (DIV2).

We define the condensation D* of a digraph D as follows: V(D*) is the set of all strong components of D, and there exists an arc (S, S’) in D* if and only if S, S’ V(D*), S S’, and there exists an arc (u, u’) in D with u S and u’ S’. Proposition 3 suggests that when we look for a minimum size directed vertex cover in DC, we may deal with the condensation DC and a subset Tr V (D*) of trivial vertices corresponding to all trivial components of DC. The advantage is that D*C is always an acyclic digraph, i.e., it does not have directed cycles.

Let Tr be a vertex subset in a digraph D. A directed vertex cover (T, F) of D is called restricted if the set R = V (D) \ (T F) is a subset of Tr.

Decision Problem 5 (Restricted Directed Vertex Cover)
Instance: An acyclic digraph D, a subset Tr ⊆ V(D), and an integer k.
Question: Does D have a restricted directed vertex cover (T, F)with size(T, F) ≤ k?

Proposition 4. The Directed Vertex Cover Problem is polynomial-time reducible to the Restricted Directed Vertex Cover Problem.

Proof. Let (D, k) be an instance of the Directed Vertex Cover Problem. We construct the condensation D* of D, and define k* = n* – n + k, where n = |V(D)| and n* = |V(D*)|. Also, Tr is the set of all trivial vertices in D*. Recall that the vertices of Tr correspond to all trivial strong components of D. We may consider (D*, Tr, k*) as an instance to the Restricted Directed Vertex Cover Problem, since D_ is an acyclic digraph.

First, suppose that the answer to the Restricted Directed Vertex Cover Problem is “yes.” It means the D* has a restricted directed vertex cover (T*, F*) of size at most k*. By definition, R* ⊆ Tr, where R* = V(D*) \ (T* F*) is the rest of (T*, F*).We define sets T and F in D: T = {xi V(D) : the strong component containing xi is in T*}, and F = {xi V(D) : the strong component containing xi is in F*}. It is easy to see that (T, F) is a directed vertex cover of D. To compute the size k of (T, F), we use the fact that |R| = |R*|, where R is the rest of (T, F). We have |R| = |V(D)| – size(T, F) = |V(D*)| – size(T*, F*) = |R*|, implying that

size(T, F) = |V(D)| – |V(D*)| + size(T*, F*) ≤ nn* + k*.

Since k* was defined as k* = n* – n + k, we obtain size(T, F) k, i.e., the answer to the Directed Vertex Cover Problem is also “yes.”

Now suppose that there exists a directed vertex cover (T, F) in D with size(T, F) k. Using Proposition 3(i) and (ii), we can define disjoint subsets T* and F* in V(D*): T* = {S : the strong component S is contained in T}, and F* = {S : the strong component S is contained in F}. It is easy to check that (T*, F*) is a directed vertex cover of D*. Moreover, Proposition 3(iv) implies that it is a restricted directed vertex cover. Finally, |R| = |R*| implies that size(T*, F*) = |V(D*)||V(D*)| + size(T, F)n* – n + k = k*.

Proposition 4 shows that it is enough to develop a polynomial-time algorithm for the Restricted Directed Vertex Cover Problem.

Vertices u and v in an acyclic digraph D are called incomparable if D has neither a directed (u, v)-path nor a directed (v, u)-path. Otherwise u and v are comparable. To prove that the Restricted Directed Vertex Cover Problem has a polynomial-time solution, we first give a criterion for a set R V(D) in an acyclic digraph D to be the rest of a restricted directed vertex cover.

Proposition 5. Let D be an acyclic digraph, and let Tr V(D). A set R V(D) in D is the rest of a restricted directed vertex cover if and only if RTr and R consists of pairwise incomparable vertices.

Proof. Necessity: The condition R Tr holds by the definition of a restricted directed vertex cover. Suppose u and v are distinct vertices in R. By Lemma 1, D contains neither a (u, v)-directed path nor a (v, u)-directed path. Thus, R consists of pairwise incomparable vertices.

Sufficiency: Now R Tr is a set of pairwise incomparable vertices. We define F as the set of all vertices in V(D) \ R that are reachable from R. That is, R = {y V(D) \ R: ∃ a directed path (x, y)-path for some x R}. Also, put T = V (D) \ (R F). We prove that (T, F) is a directed vertex cover of D. Suppose it is not, i.e., there exists an arc (u, v) such that u T and v F. There are two cases to consider.

Case 1. u F

According to the definition of F, u F implies that there exist a vertex w R and a directed (w, u)-path P. Now, P (u, v) is a directed (w, v)-path, therefore v must be in F, a contradiction to v F.

Case 2. U R

Since v is reachable from the vertex u R, we have v F, a contradiction.

Thus, each case produces a contradiction, so (T, F) is a directed vertex cover of D.

Recall that a finite poset [a partially ordered set] is an ordered pair P = (X, ≤) consisting of a finite set X and a binary relation ≤ that satisfies

(Reflexivity): xx,

(Antisymmetry): xy and yx imply x = y, and

(Transitivity): xy and yz imply xz for all x, y, z X.

A poset P = (X, ≤) defines an acyclic digraph D = Hasse(P) called the Hasse diagram of P: its vertex-set is X, and (x, y) is an arc of D if and only if x covers y. Antisymmetry implies that Hasse(P) has no directed cycles. Note that an arbitrary acyclic digraph D is not necessarily the Hasse diagram of a poset. However, an acyclic digraph D uniquely defines a poset (V(D), ≤), the poset of D, on X = V(D): x ≤ y for x, y X if and only if there exists a directed (y, x)-path in D.

Definition 4

The comparability graph of a poset P = (X, ) is the graph with vertex-set X in which distinct vertices x and y are adjacent if and only if x and y are comparable in P, that is either x ≤ y or y ≤ x.

We extend Definition 4 to all acyclic digraphs: the comparability graph of a digraph D is defined as the comparability graph of the poset of D. As an illustration, let us consider the following poset P defined on {2, 3, 4, 6, 8} by xy if and only if x divides y. Figure 1 shows the Hasse diagram H of P, an equivalent acyclic digraph D [P is the poset of D],  and their common comparability graph G.

Proposition 6. The Restricted Directed Vertex Cover Problem can be solved in polynomial time.

Proof. To find a minimum size restricted directed vertex cover in an acyclic digraph D is the same as to find a maximum set R Tr that can be the rest of a directed vertex cover.

To construct such a set R, we use Proposition 5: R must be a largest subset of Tr consisting of pairwise incomparable vertices. Let us consider the comparability graph G of D. Recall that distinct vertices are incomparable in D if and only if they are non-adjacent in G. Thus, it is sufficient to find a maximum independent set S Tr in G.

Decision Problem 6 (Independent Set)
Instance: A graph G, and an integer k.
Question: Does G have a independent set S with |S| ≥ k?

This problem is the complementary form of the Vertex Cover Problem, and it is NP-complete in general. However, we have this problem for the class of all comparability graphs of acyclic digraphs which is the same as the class of all comparability graph of posets. For comparability graphs, the Independent Set Problem can be solved in polynomial time, see Golumbic . Finally, the condition that we need a maximum independent set within Tr can be easily satisfied. Indeed, the subgraph G’ of G induced by Tr is again a comparability graph, so we may apply a polynomial-time algorithm for the Independent Set Problem to G’.

We have established Theorem 1.

One may think that the Directed Vertex Cover Problem is hard, since it is very similar to the Vertex Cover Problem for undirected graphs. However, Theorem 1 and Proposition 2 imply the following unexpected result.

Corollary 1. The Directed Vertex Cover Problem can be solved in polynomial time.

Boolean Polynomials

We now turn to Boolean polynomials P(x1, x2, …, xn) = T1 ⊕ T2 ⊕ . . . Tm, where each term is a product of some distinct variables of {x1, x2, …, xn}, and ⊕ denotes mod 2 addition. Note that we treat Boolean polynomials as Boolean functions (not as formal polynomials), so x2 x for every variable x. The following facts are well-known, see for example Rosen .

Proposition 7. (i) Every Boolean function has a CNF representation.
(ii) Every Boolean function has a DNF representation.
(iii) Every Boolean function can be represented as a Boolean polynomial.

Unlike CNF and DNF representations, the Boolean polynomial representation is unique. Every Boolean polynomial defines exactly one Boolean function. Thus, the Boolean polynomial representation of a Boolean function is unique if and only if the number of distinct Boolean polynomials equals the number of distinct Boolean functions. Let f be a Boolean function of n variables. There are two possibilities (0 and 1) for the value of f at each of the 2n = |Bn| points in its domain. Hence, there are exactly 22^n Boolean functions of n variables. Now we count the number of Boolean polynomials in n variables. Each of the n variables either participates in a term or not; thus, there are exactly 2n possible terms. To produce a particular polynomial is to choose 0–1 coefficients for the 2n terms. Hence, there are exactly 22^n Boolean polynomials in n variables.

What about satisfiability/unsatisfiability for Boolean polynomials? Every polynomial P 0 takes value 1, and every polynomial P 1 takes value 0 at some points. This follows from the uniqueness of Boolean polynomials. Thus, the satisfiability/unsatisfiability problems for polynomials are easy. But these are just decision problems. To solve the corresponding search problem, we must find a particular point that gives value 1 or 0 to P (or show that no such point exists). We give solutions to the search satisfiability/unsatisfiability problems for polynomials as an example.

Example 1. Let P(x1, x2, . . ., xn) be a Boolean polynomial. If it is a constant, then the search satisfiability/unsatisfiability problems are trivial. If P is not a constant, then we consider two projections with respect to x1: P|x1=0 = P(0, x2, . . ., xn), and P|x1=1 = P(1, x2, . . ., xn). Suppose that both P|x1=0 and P|x1=1 are constant, say c0 and c1, respectively. Since P is not a constant, we must have c0c1, and we have obtained solutions to the both problems.

Suppose now that at least one of P|x1=0 or P|x1=1 is not a constant, say P0 = P|x1=0 ≢ const. Then, P0 takes both 0 and 1 at some points of Thus, we fix value of x1 as x1 = 0, and continue the process with P0.

Thus, there is a linear-time algorithm to solve the search satisfiablity/unsatisfiablity problems for polynomials.

We now turn to partial assignments. A partial assignment xo to X satisfies a polynomial P if P(xo) ≡ 1.

Decision Problem 7 (Minimum True Assignment for Polynomials)
Instance: A Boolean polynomial P over X and an integer k.
Question: Is there a partial assignment to X of size at most k that satisfies P?

Decision Problem 8 (Minimum False Assignment for Polynomials)
Instance: A Boolean polynomial P over X and an integer k.
Question: Is there a partial assignment to X of size at most k that makes P 0?

(These problems are equivalent within the class of all Boolean polynomials. Indeed, a partial assignment to X of size at most k makes P 1 if and only if it makes P 1 ≡ 0. However, as we will see, they are not equivalent within the class of bilinear polynomials.)

The optimization versions of Decision Problem 2 and Decision Problem 3 are to find minimum size partial assignments that make a given polynomial an identical 1 or an identical 0, respectively.

Example 2. Let us consider a linear polynomial P = x1 x2⊕. . . ⊕ xm c, where c ∈ {0, 1} is a constant. If c = 0 then P is called purely linear. Let xo be a partial assignment to X that satisfies P. If at least one variable in xo is undefined, then the resulting linear polynomial P(xo) is not a constant. Hence we must specify values of all variables, obtaining a partial assignment of size m. To get 1, we set all variables to 0 if c = 1. If c = 0 then we define xio = 1 and xio = 0 for all i ∈{2, 3, . . .,m}.

A similar situation takes place for the Minimum False Assignment Problem – we have to specify the values of all variables.

Proposition 8. Both the Minimum True Assignment Problem and the Minimum False Assignment Problem for linear polynomials can be solved in linear time.

As the next step, it is natural to consider quadratic polynomials, that is Boolean polynomials of degree at most two. They are of the form P = Q L c, where each term in Q is of the form xixj, L consists of linear terms, and c ∈ {0, 1} is a constant.

Theorem 2. Within quadratic Boolean polynomials,
(i) the Minimum True Assignment Problem is NP-complete, and
(ii) the Minimum False Assignment Problem is NP-complete.

Proof. First, observe that both problems are in NP. Indeed, since the Satisfiability Problem is polynomial-time solvable even in its search version, we can check in polynomial time whether a given partial assignment satisfies a given Boolean polynomial (and is of the right size). Similarly, the Minimum False Assignment Problem is in NP. Next, we show that both Problems are NP-hard.

(i) We construct a linear-time reduction from the Vertex Cover Problem.

Given an instance (G, k) to the Vertex Cover Problem, we consider the vertex-set X = V(G) of G as a set of Boolean variables: X = {x1, x2, . . ., xn}. Now we define an instance (P, k) to the Minimum True Assignment Problem with a quadratic polynomial P. Note that we use the same k as in (G, k). For each edge e = {xi, xj} of G, we create the corresponding term Te = xixj in P, and we define P(x1, x2, . . ., xn) = Te1 Te2 ⊕ . . . ⊕ Tem ⊕ 1, where {e1, e2, . . ., em} is edge-set of G. The polynomial P can be constructed in linear time in m.

Fact 1. If the answer to the Minimum True Assignment Problem for (P, k) is yes, then the answer to the Vertex Cover Problem for (G; k) is also yes.

Proof. We are given that there exists a partial true assignment xo of size at most k that satisfies P. Note that each quadratic term xixj of P must contain a variable, say xi, such that xio ∈ {0, 1}. Indeed, otherwise the polynomial P(xo) contains a quadratic term, and therefore it is not a constant. By our construction, the specified variables in xo constitute a vertex cover T in G. Denoting by s be the total number of specified variables in xo, we obtain k ≥ size(xo) = |T|. Thus, the answer to the Vertex Cover Problem for (G, k) is “yes,” as required.

Now we prove the converse.

Fact 2. If the answer to the Vertex Cover Problem for (G, k) is yes, then the answer to the Minimum True Assignment Problem for (P, k) is also yes.

Proof. Suppose G has a vertex cover T of size at most k. Using T, we construct a partial truth assignment xo for X as follows. Whenever xi T, we set xio = 0. All other components of xo are undefined. Clearly, size(xo) = |T|k. It remains to show that xo satisfies P. Since T is a vertex cover, each edge of G has at least one of its end-vertices in T. Using the definitions of P and xo, we see that each term of P has at least one variable xi with = 0. Thus, P(xo) ≡ 1.

Fact 1 and Fact 2 show that the Vertex Cover Problem is linear-time reducible to the Minimum True Assignment Problem for quadratic polynomials, and the result follows from NP-completeness of the Vertex Cover Problem.

(ii) This part is similar to (i). We just modify the definition of P, namely we set P(x1, x2, . . ., xn) = Te1 Te2 ⊕ . . . ⊕ Tem, where {e1, e2, . . ., em} is edge-set of G.

Next, we consider bilinear polynomials. Bilinear polynomials constitute an intermediate class between linear polynomials, for which the problems are easy, and quadratic polynomials, for which the problems are hard.

Definition 5. A Boolean polynomial P is called bilinear if it can be represented as product of two linear polynomials.

For example, P = x1 + x1x2 + x1x3 +x2x3 = (x1 x2) ∙ (x1 x3) is a bilinear polynomial. Before presenting our main result, we give some preliminary results.

Lemma 2. If 1L1 L2 for linear polynomials L1 and L2, then L1 ≡ 1 and L2 ≡ 1.

Proof. We have L1L2(xo) = L1(xo)L2(xo) ≡ 1 for every assignment xo. Recall that every polynomial P 1 achieves value 0. Thus, L1(xo) ≡ 1 and L2(xo) ≡ 1 for every xo. Hence, L1 ≡ 1 and L2 ≡ 1.

0 has more representations as a product of two linear polynomials.

Lemma 3. If 0 ≡ L1L2 for linear polynomials L1 and L2, then either

(Zero Term): Li ≡ 0 for some i ∈ {1, 2}, or

(Complementary Terms): L1 = L2 ⊕ 1.

Proof. Let Li = Q Ri ci for i = 1, 2, where Q is the common part of L1 and L2 excluding the constants c1, c2 ∈ {0, 1}. The quadratic part QR1 QR2 R1R2 of L1L2 must be 0; therefore at least two of Q, R1, R2 are identically zero.

Case 1. If Q ≢ 0 then R1 ≡ 0 and R2 ≡ 0. We have L1 = Q c1 and L2 = Q c2, sp

L1L2 = (Q c1)(Q c2) = (1 ⊕ c1 c2)Q c1c2. (1)
If the coefficient of Q, 1 ⊕ c1 c2, is not zero, then L1L2 is not a constant, a contradiction. Thus, 1 ⊕ c1 c2 = 0 meaning that c1 = c2 ⊕ 1. Thus, L1 = Q ⊕ c1 = Q ⊕ c2 ⊕ 1 = L2 ⊕ 1, giving (Complementary Terms).

Case 2. If Q ≡ 0 then at least one of R1, R2 must be 0. By symmetry, we may assume that R1 ≡ 0, and therefore L1 = c1 and L2 = R2 c2. If c1 = 0 then the condition (Zero Term) holds, since L1 ≡ 0. If c1 = 1 then L1L2 = L2 = R2 c2. To get L1L2 ≡ 0, we must have R20 and c2 = 0. Thus, L2 ≡ 0 and the condition (Zero Term) holds.

Now we give efficient solutions to the Minimum True/False Assignment Problems.

Theorem 3. Within bilinear polynomials,
(i) the Minimum True Assignment Problem can be solved in polynomial time, and
(ii) the Minimum False Assignment Problem can be solved in polynomial time.

Proof. Let P be a bilinear polynomial. Let L1L2 be a bilinear representation of P. Note that L1 and L2 are not constants, since P is not a linear polynomial.

(i) Suppose that xo is a solution to the Minimum True Assignment Problem for P, that is P(xo) = L1L2(xo) ≡ 1. We have L1L2(xo) = L1(xo)L2(xo) ≡ 1: According to Lemma 1, L1(xo) ≡ 1 and L2(xo) ≡ 1. Thus, all variables in L1 and in L2 must be specified. But the variables of L1 and L2 constitute the set of all variables of P. Thus, we have the Satisfiability Problem for polynomials, which is simple even in its search version, see Example 1.

(ii) Now let xo be a solution to the Minimum False Assignment Problem for P, that is P(xo) = L1L2(xo) ≡ 0. We have L1L2(xo) = L1(xo)L2(xo) ≡ 0: According to Lemma 2, there are two possibilities described in the conditions (Zero Term) and (Complementary Terms).

To satisfy the condition (Zero Term) in an optimal way, we should choose a term Li ∈ {L1, L2} with the minimum number, m1, of variables. It is always possible to make Li = 0 assigning appropriate values to the variables of Li. Indeed, if Li(0, 0, . . ., 0) = 1 then we can change the value of one variable only to obtain 0. Recall that each Li is not a constant, and therefore it has at least one variable. Let us consider the condition (Complementary Terms). We have

L1(xo) ≡ L2(xo) ⊕ 1.     (2)

Let L1 = Q R1 c1 and L2 = Q R2 c2, where Q is the common part of L1 and L2 excluding the constants c1 and c2. Applying (2), we obtain Q(xo) ⊕ R1(xo) ⊕ c1 Q(xo) ⊕ R2(xo) ⊕ c2 ⊕ 1, or

R1(xo) ⊕ c1 R2(xo) ⊕ c2 ⊕ 1.    (3)

As it is clear from (3), both R1(xo) and R2(xo) must be constants, since R1 and R2 have disjoint sets of variables. If R1 ≡ 0 and R2 ≡ 0, then L1 = Q ⊕ c1 and L2 = Q ⊕ c2. L1L2 is linear if c1 = c2, which is impossible. Thus, c1c2, so (3) holds. If there is at least one variable in R1R2, then it is easy to specify values of all the variables in R1R2 to satisfy (3). Let m2 be the number of variables in R1R2.

Now let m = min{m1, m2}, where the number m1 and m2 are defined above. It follows that to solve the Minimum False Assignment Problem for P, we should find m variables involved in a bilinear representation of P, and specify their values in such a way that the corresponding condition (Zero Term) or (Complementary Terms) is satisfied. As we have seen, it always can be done.

Concluding discussion

There are three well-known classes of CNF formulas where the SAT Problem can be solved efficiently: 2-SAT, Horn SAT, and READ-2 SAT. Proposition 1 implies that the Minimum Assignment Problem is NP-complete within 2-CNF formulas and within Horn CNF formulas. Our Theorem 1 gives a class in the intersection of the classes of 2-CNFs and Horn CNF formulas for which the problem is tractable.

We also investigate the Minimum True and Minimum False Assignment Problems for Boolean polynomials. We prove that the problems are easy for linear polynomials, but are NP-complete for quadratic polynomials. Our main result is that both the Partial True Assignment Problem and the Partial False Assignment Problem for bilinear polynomials can be solved efficiently. The two problems are not similar within the class of bilinear polynomials: the algorithm for the Partial False Assignment Problem is more complicated than that for the Partial True Assignment Problem. The proof of Theorem 2 shows that the Minimum True Assignment Problem for bilinear polynomials is essentially the same as the Satisfiability Problem for such polynomials. To solve its search version we may use the simple algorithm of Example 1. Our polynomial algorithm for the Minimum False Assignment Problem for bilinear polynomials, given in the proof of Theorem 2, is more involved.

A promising direction for further research is to discover new classes of CNF formulas where the Minimum Assignment Problem is tractable. It is also interesting to investigate the Minimum True/False Assignment Problems for multilinear polynomials. In particular, it would be interesting to know whether the problems are tractable for Boolean polynomials that can be represented as product of three linear polynomials.

References

S. A. Cook, The complexity of theorem proving procedures, in: Proceedings 3rd Annual ACM Symposium on Theory of Computing (ACM, New York, 1971) 151–178

W. F. Dowling and J. H. Gallier, Linear-time algorithms for testing the satisfiability of propositional Horn formulae, J. Logic Programming 1 (3) (1984) 267–284

M. R. Garey and D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness (W. H. Freeman and Co., San Francisco, Calif., 1979) x+338 pp.

M. Ch. Golumbic, Algorithmic graph theory and perfect graphs (Academic Press, New York, 1980) xx+284 pp.

K. G. Murty and C. Perin, A 1-matching blossom-type algorithm for edge covering problems, Networks 12 (4) (1982) 379–391

K. H. Rosen, Discrete Mathematics and its applications, Fifth Edition (The McGraw-Hill Co., Inc., Boston e. a., 2003) xxi+787 pp.

C. A. Tovey, A simplified NP-complete satisfiability problem, Discrete Appl. Math. 8 (1) (1984) 85–89

1. In the Supplement, we show that bilinear polynomials can be recognized in polynomial time. We also show that all representations of a bilinear polynomial as a product of two linear polynomials can be constructed in polynomial time.
SHARE