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 = *(*x _{1}, x_{2}, *…

*,x*) be an ordered set of 0–1 variables. A

_{n}*literal*over

*X*is either a variable

*x*

*∈*

*X*[

*positive*literal] or its

*negation (x-bar)*

*= 1 – x*

_{i}*[*

_{i }*negative*literal]. Denote the set of literals over

*X*by

*L*. A truth assignment to

_{X}*X*is a point

*x*= (

^{o}*x*

_{1}^{o}*, x*,…,

_{2}^{o}*x*)of the

_{n}^{o}*n*-dimensional Boolean cube B

^{ }

^{n}*= {0,1}*

^{n}A *Boolean function* is a mapping *ƒ*: B^{n}* *→B. There are three main representations of an arbitrary Boolean function *ƒ* over *X*:

*conjunctive normal form* [CNF]: *C *= *C _{1}C_{2}…C_{m}* where each

*clause*

*C*is disjunction of some literals of

_{i}*X*(and

*C*is the conjuction of

_{i}C_{j}*C*and

_{i}*C*),

_{j}*disjunctive normal form* [DNF]: *D* = *T _{1 }*∨

*T*∨. . .∨

_{2 }*T*where each

_{m}*term T*is conjunction of some literals of

_{i}*X*, and

*Boolean polynomial*: *P* = *T _{1 }*⊕

*T*⊕ . . . ⊕

_{2 }*T*where each

_{m}*term T*is product of some variables of

_{i}*X*, and ⊕ denotes mod 2 addition.

A truth assignment x^{o}*satisfies* a Boolean formula *f *if *f*(x* ^{o}*) = 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 *k*–*CNF*, then SAT is called the *k*–*SAT* 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 [3].

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 x* ^{o}* of Boolean values to at most

*k*of the variables that satisfies

*C*, in the sense that

*C*(x

*) 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.*

^{o}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 = *(*x _{1}, x_{2}, *…

*,x*)

_{n}

*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*x

*size(x*

^{o},*)*

^{o}*, is defined as the total number of zeroes and ones in*x

^{o}.* *

* *

For example, (0, c, 1, ✴) is a partial assignment of size two to (*x*_{1}, *x*_{2}, *x*_{3}, *x*_{4}) with *x*_{1} = 0, *x*_{3} = 1, and with undefined values of *x*_{2} and *x*_{4}. In general, if *c _{j}*∈

*C*is a clause and x

*is a partial assignment to*

^{o}*X*,

*c*(x

_{j}*) is a Boolean function, since the values of all variables*

^{o}*x*of

_{i}*c*with

_{j}*x*= ✴ are undefined. If

_{i}^{o}*c*(x

_{j}*) evaluates to 1 for every assignment of the undefined variables, we say*

^{o}*c*(x

_{j}*) ≡1 and x*

^{o}

^{o}*satisfies*

*c*.

_{j}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* = *c*_{1}*c*_{2}*c*_{3}, where *c*_{1} = (*x*_{1 }∨ x_{2}), *c*_{2} = (*x*_{1 }∨ *x*_{3}), *c*_{3} = (*x*_{2 }∨ *x*_{3}). If *x*_{1} = 1 then *c*_{1} is satisfied, *x*_{3} = 1 [to satisfy *c*_{2}], and *c*_{3} is satisfied by *x*_{3}. We obtain a partial assignment (1, ✴, 1) of size 2 satisfying *C*. Setting *x*_{1} = 0, we obtain (0, 0, 1), a partial assignment of size 3. Finally, if *x*_{1} = ✴ 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* = {*c _{e}* :

*e*∈

*E*} over

*X*by the following:

*c*= (

_{e}*x*∨

_{i }*x*) for each edge

_{j}*e*=

*x*of

_{i }x_{j}*G*.

If *T* is a vertex cover in *G* with |*T*| ≤ *k*, then *C* is satisfied by the following partial assignment x* ^{T}* of size |

*T*|: = 1 if

*x*, and = ✴ otherwise.

_{i}^{T}Conversely, let x* ^{o}* be a partial assignment of size at most

*k*satisfying

*C*. The vertices corresponding to ones of x

*constitute a vertex cover*

^{o}*T*in

^{o}*G*with |

*T*| ≤

^{o}*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 [2]. 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 *D _{C}* = (

*X*,

*A*) as follows: there exists an arc (

*x*,

_{i}*x*) in

_{j}*D*if and only if (

_{C}*x*∨

_{i}*x*) ∈

_{j}*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)**: *u* ∈ *T, or*

**(DIV2)**: *v* ∈ *F.*

*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 *D _{C}* and

*k*as an instance to the Directed Vertex Cover Problem.

Suppose that *D _{C}* has a directed vertex cover (

*T*,

*F*) with size(

*T*,

*F*)

*≤*k. Using

*T*and

*F*, we define a partial truth assignment x

*to*

^{o}*X*by

Clearly, size(x* ^{o}*) = size(

*T*,

*F*) ≤

*k*. We show that x

*satisfies*

^{o}*C*. Indeed, let be an arbitrary clause of

*C*. Accordingly, (

*x*,

_{i}*x*) is an arc of the digraph

_{j}*D*. By Definition 3, either (DIV1) or (DIV2) holds for the arc (

_{C}*x*,

_{i}*x*). If (DIV1) holds then

_{j}*x*∈

_{i }*T*, and therefore = 1, implying that x

*satisfies*

^{o}*C*. If

*x*∈

_{j }*F*[the condition (DIV2)], then = 0, and again x

*satisfies*

^{o}*C*. Thus, Directed Vertex Cover is polynomial-time reducible to Minimum Assignment.

Conversely, suppose that there exists a partial assignment x* ^{o}* to

*X*of size at most

*k*that satisfies

*C*. We define disjoint subsets

*T*and

*F*of

*V*(

*D*) by

_{C}*T*= {

*x*:

_{i}*x*= 1} and

_{j}^{o }*F*= {

*x*:

_{i}*x*= 0}. It is easy to see that both (DIV1) and (DIV2) hold for (

_{j}^{o}*T*,

*F*). Hence (

*T*,

*F*) is a directed vertex cover of

*D*with size(

_{C}*T*,

*F*) = size(x

*)*

^{o}*≤*

*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* = *u*_{1}, *u*_{2}, …, *u _{k}* =

*v*) in

*S*. For the arc (

*u*

_{1},

*u*

_{2}) the condition (DIV1) does not hold, therefore

*u*

_{2}∈

*F*according to (DIV2). Continuing inductively, we get

*u*∈

_{t }*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 *D _{C}*, we may deal with the condensation

*D*and a subset

_{C}*Tr*⊆

*V (D*)*of

*trivial vertices*corresponding to all trivial components of

*D*The advantage is that

_{C}.*D**is always an

_{C}*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* = {*x _{i }*∈

*V(D)*: the strong component containing

*x*is in

_{i}*T**}, and

*F = {x*∈

_{i}*V(D)*: the strong component containing

*x*is in

_{i}*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**) ≤ *n* – *n** + *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):** *x* ≤ *x*,

**(Antisymmetry):** *x* ≤ *y* and *y* ≤ *x* imply *x* = *y*, and

**(Transitivity):** *x* ≤ *y* and *y* ≤ *z* imply *x* ≤ *z* 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 *x* ≤ *y* 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 [4]. 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*(*x*_{1}, *x*_{2}, …, *x*_{n}) = *T*_{1 }⊕ T_{2 }⊕ . . . T_{m}, where each term is a product of some distinct variables of {*x*_{1}, *x*_{2}, …, *x _{n}*}, and ⊕ denotes mod 2 addition. Note that we treat Boolean polynomials as Boolean functions (not as formal polynomials), so

*x*≡

^{2 }*x*for every variable

*x*. The following facts are well-known, see for example Rosen [6].

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 2* ^{n}* = |B

*| points in its domain. Hence, there are exactly 2*

^{n}^{2^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 2

*possible terms. To produce a particular polynomial is to choose 0–1 coefficients for the 2*

^{n}*terms. Hence, there are exactly 2*

^{n}^{2^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*(*x*_{1}, *x*_{2}, . . ., *x _{n}*) 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

*x*

_{1}:

*P*|

_{x}_{1=0}=

*P*(0,

*x*

_{2}, . . .,

*x*), and

_{n}*P*|

_{x}_{1=1}=

*P*(1,

*x*

_{2}, . . .,

*x*). Suppose that both

_{n}*P*|

_{x}_{1=0}and

*P*|

_{x}_{1=1}are constant, say

*c*

_{0}and

*c*

_{1}, respectively. Since

*P*is not a constant, we must have

*c*

_{0}≠

*c*

_{1}, and we have obtained solutions to the both problems.

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

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 x* ^{o}* to

*X*

*satisfies*a polynomial

*P*if

*P*(x

*) ≡ 1.*

^{o}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* = *x*_{1}⊕* x*_{2}⊕. . . ⊕* x _{m}*⊕

*c*, where c ∈ {0, 1} is a constant. If

*c*= 0 then

*P*is called

*purely linear*. Let x

*be a partial assignment to*

^{o}*X*that satisfies

*P*. If at least one variable in x

*is undefined, then the resulting linear polynomial*

^{o}*P*(x

*) is not a constant. Hence we must specify values of all variables, obtaining a partial assignment of size*

^{o}*m*. To get 1, we set all variables to 0 if

*c*= 1. If

*c*= 0 then we define

*x*

_{i}^{o}*= 1 and*

*x*= 0 for all

_{i}^{o}*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 *x _{i}x_{j}*,

*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* = {*x*_{1}, *x*_{2}, . . ., *x _{n}*}. 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*= {

*x*,

_{i}*x*} of

_{j}*G*, we create the corresponding term

*T*=

_{e}*x*in

_{i}x_{j}*P*, and we define

*P*(

*x*

_{1},

*x*

_{2}, . . .,

*x*) =

_{n}*T*

_{e}_{1}⊕

*T*

_{e}_{2}⊕ . . . ⊕

*T*⊕ 1, where {

_{em}*e*

_{1},

*e*

_{2}, . . .,

*e*} is edge-set of

_{m}*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 *x _{i}x_{j}* of

*P*must contain a variable, say

*x*, such that

_{i}*x*∈ {0, 1}. Indeed, otherwise the polynomial

_{i}^{o}*P*(x

*) contains a quadratic term, and therefore it is not a constant. By our construction, the specified variables in x*

^{o}*constitute a vertex cover*

^{o}*T*in

*G*. Denoting by

*s*be the total number of specified variables in x

*, we obtain*

^{o}*k*≥ size(x

*) =*

^{o}*|*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 x* ^{o}* for

*X*as follows. Whenever

*x*∈

_{i}*T*, we set

*x*= 0. All other components of x

_{i}^{o}*are undefined. Clearly, size(x*

^{o}*) =*

^{o}*|T|*≤

*k*. It remains to show that x

*satisfies*

^{o}*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 x

*, we see that each term of*

^{o}*P*has at least one variable

*x*with = 0. Thus,

_{i}*P*(x

*) ≡ 1.*

^{o}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*(*x*_{1}, *x*_{2}, . . ., *x _{n}*) =

*T*

_{e}_{1}⊕

*T*

_{e}_{2}⊕ . . . ⊕

*T*, where {

_{em}*e*

_{1},

*e*

_{2}, . . .,

*e*} is edge-set of

_{m}*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* = *x*_{1} + *x*_{1}*x*_{2} + *x*_{1}*x*_{3} +*x*_{2}*x*_{3} = (*x*_{1} ⊕* x*_{2}) ∙ (*x*_{1} ⊕* x*_{3}) is a bilinear polynomial. Before presenting our main result, we give some preliminary results.

Lemma 2. *If *1*L*_{1} ≡* L*_{2}* for linear polynomials L*_{1}* and L*_{2}*, then L*_{1} ≡ 1* and L*_{2} ≡ 1*.*

* *

* *

*Proof*. We have *L*_{1}*L*_{2}(x* ^{o}*) =

*L*

_{1}(x

*)*

^{o}*L*

_{2}(x

*) ≡ 1 for every assignment x*

^{o}*. Recall that every polynomial*

^{o}*P*≢

*1 achieves value 0. Thus,*

*L*

_{1}(x

*) ≡ 1 and*

^{o}*L*

_{2}(x

*) ≡ 1 for every x*

^{o}*. Hence,*

^{o}*L*

_{1}≡ 1 and

*L*

_{2}≡ 1.

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

Lemma 3. If 0 ≡* L*_{1}*L*_{2} for linear polynomials *L*_{1} and *L*_{2}, then either

**(Zero Term):** *L _{i}* ≡ 0

*for some i*∈ {

*1, 2*}

*, or*

**(Complementary Terms):** *L*_{1} = *L*_{2} ⊕ 1.

*Proof*. Let *L _{i}* =

*Q*⊕

*R*⊕

_{i}*c*for

_{i}*i*= 1, 2, where

*Q*is the common part of

*L*

_{1}and

*L*

_{2}excluding the constants

*c*

_{1},

*c*

_{2}∈ {0, 1}. The quadratic part

*QR*

_{1}⊕

*QR*

_{2}⊕

*R*

_{1}

*R*

_{2}of

*L*

_{1}

*L*

_{2}must be 0; therefore at least two of Q,

*R*

_{1},

*R*

_{2}are identically zero.

Case 1. If Q ≢ 0 then *R*_{1} ≡ 0 and *R*_{2} ≡ 0. We have *L*_{1} = *Q* ⊕* c*_{1} and *L*_{2} = *Q* ⊕* c*_{2}, sp

*L*_{1}*L*_{2} = (*Q* ⊕* c*_{1})(*Q* ⊕* c*_{2}) = (1 ⊕* c*_{1} ⊕* c*_{2})*Q* ⊕* c*_{1}*c*_{2}. (1)

If the coefficient of *Q*, 1 ⊕* c*_{1} ⊕* c*_{2}, is not zero, then *L*_{1}*L*_{2} is not a constant, a contradiction. Thus, 1 ⊕* c*_{1} ⊕* c*_{2} = 0 meaning that *c*_{1} = *c*_{2} ⊕ 1. Thus, *L*_{1} = Q ⊕* c*_{1} = Q ⊕* c*_{2} ⊕ 1 = *L*_{2} ⊕ 1, giving (Complementary Terms).** **

Case 2. If Q ≡ 0 then at least one of *R*_{1}, *R*_{2} must be 0. By symmetry, we may assume that *R*_{1} ≡ 0, and therefore *L*_{1} = *c*_{1} and *L*_{2} = *R*_{2} ⊕* c*_{2}. If *c*_{1} = 0 then the condition (Zero Term) holds, since *L*_{1} ≡ 0. If *c*_{1} = 1 then *L*_{1}*L*_{2} = *L*_{2} = *R*_{2} ⊕* c*_{2}. To get *L*_{1}*L*_{2} ≡ 0, we must have *R*_{2}0 and *c*_{2} = 0. Thus, *L*_{2} ≡ 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. ^{[1]}Let *L*_{1}*L*_{2} be a bilinear representation of *P*. Note that *L*_{1} and *L*_{2} are not constants, since *P* is not a linear polynomial.

(i) Suppose that x* ^{o}* is a solution to the Minimum True Assignment Problem for

*P*, that is

*P*(x

*) =*

^{o}*L*

_{1}

*L*

_{2}(x

*) ≡ 1. We have*

^{o}*L*

_{1}

*L*

_{2}(x

*) =*

^{o}*L*

_{1}(x

*)*

^{o}*L*

_{2}(x

*) ≡ 1: According to Lemma 1,*

^{o}*L*

_{1}(x

*) ≡ 1 and*

^{o}*L*

_{2}(x

*) ≡ 1. Thus, all variables in*

^{o}*L*

_{1}and in

*L*

_{2}must be specified. But the variables of

*L*

_{1}and

*L*

_{2}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 x* ^{o}* be a solution to the Minimum False Assignment Problem for P, that is P(x

*) =*

^{o}*L*

_{1}

*L*

_{2}(x

*) ≡ 0. We have*

^{o}*L*

_{1}

*L*

_{2}(x

*) =*

^{o}*L*

_{1}(x

*)*

^{o}*L*

_{2}(x

*) ≡ 0: According to Lemma 2, there are two possibilities described in the conditions (Zero Term) and (Complementary Terms).*

^{o}To satisfy the condition (Zero Term) in an optimal way, we should choose a term *L _{i }*∈ {

*L*

_{1},

*L*

_{2}} with the minimum number,

*m*

_{1}, of variables. It is always possible to make

*L*= 0 assigning appropriate values to the variables of

_{i}*L*. Indeed, if

_{i}*L*(0, 0, . . ., 0) = 1 then we can change the value of one variable only to obtain 0. Recall that each

_{i}*L*is not a constant, and therefore it has at least one variable. Let us consider the condition (Complementary Terms). We have

_{i}*L*_{1}(x* ^{o}*) ≡

*L*

_{2}(x

*) ⊕ 1. (2)*

^{o}Let *L*_{1} = *Q *⊕ *R*_{1 }⊕ *c*_{1} and *L*_{2} = *Q*_{ }⊕ *R*_{2 }⊕ *c*_{2}, where *Q* is the common part of *L*_{1} and *L*_{2} excluding the constants *c*_{1} and *c*_{2}. Applying (2), we obtain *Q*(x* ^{o}*) ⊕

*R*

_{1}(x

*) ⊕*

^{o}*c*

_{1 }≡

*Q*(x

*) ⊕*

^{o}*R*

_{2}(x

*) ⊕*

^{o}*c*

_{2}⊕ 1, or

*R*_{1}(x* ^{o}*) ⊕

*c*

_{1 }≡

*R*

_{2}(x

*) ⊕*

^{o}*c*

_{2}⊕ 1. (3)

As it is clear from (3), both *R*_{1}(x* ^{o}*) and

*R*

_{2}(x

*) must be constants, since*

^{o}*R*

_{1}and

*R*

_{2}have disjoint sets of variables. If

*R*

_{1 }≡ 0 and

*R*

_{2 }≡ 0, then

*L*

_{1}= Q ⊕

*c*

_{1}and

*L*

_{2}= Q ⊕

*c*

_{2}.

*L*

_{1}

*L*

_{2}is linear if

*c*

_{1}=

*c*

_{2}, which is impossible. Thus,

*c*

_{1}≠

*c*

_{2}, so (3) holds. If there is at least one variable in

*R*

_{1}

*R*

_{2}, then it is easy to specify values of all the variables in

*R*

_{1}⊕

*R*

_{2}to satisfy (3). Let

*m*

_{2}be the number of variables in

*R*

_{1}⊕

*R*

_{2}.

Now let *m* = min{*m*_{1}, *m*_{2}}, where the number *m*_{1} and *m*_{2} 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

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.↩^{[1]}