February 14, 2017 at 14:45Mixing with the use of “regulators”: the feasibility problem
Hi, habrozhiteli! We decided to publish an excerpt from the book Algorithms: Development and Application. Classic Computers Science. " Tasks SAT and 3-SAT . Suppose there is a set X of n Boolean variables x1, ..., xn; each variable can take the value 0 or 1 (equivalent to false and true). A literal over X is one of the variables xi or its negation. Finally, the condition is called the ordinary disjunction of literals
Now let us give a formal definition to the assignment of values that satisfy a set of conditions. Logical assignment for X is the assignment of a value of 0 or 1 to each xi; in other words, this is the function ν: X → {0,1}. Assignment v implicitly sets the truth value to be opposite to xi. Assignment fulfills condition C if after it C gives result 1 according to the conditions of Boolean logic; this is equivalent to the requirement that at least one of the literals in C has a value of 1. Assignment satisfies the set of conditions C1, ..., Ck if as a result all Ci give the result 1; in other words, if as a result of its conjunction
The logical assignment ν, which sets all three variables to 1, is not fulfilling because the second of the listed conditions is not satisfied; on the other hand, the assignment ν ', which sets all variables to 0, is fulfilling.
Now we can give a statement of the satisfiability problem, also denoted by SAT:
For a given set of conditions C1, ..., Ck with respect to the set of variables X = {x1, ..., xn} is there a logical assignment?
There is a special case of SAT, which has equivalent complexity, but is more clear; all conditions in it contain exactly three literals (corresponding to different variables). We call this task the 3-feasibility problem, or 3-SAT:
For a given set of conditions C1, ..., Ck, each of which has a length of 3, with respect to the set of variables X = {x1, ..., xn}, is there a logical assignment?
The feasibility and 3-feasibility problems are fundamental tasks of combinatorial search; they contain the main components of a complex computational task and in an extremely simplified form. It is required to take n independent decisions (assignment to all xi) so as to fulfill a set of constraints. There are different ways to fulfill each constraint individually, but decisions will have to be combined so that all constraints are met simultaneously.
Now, we will connect the computational complexity embodied in the SAT and 3-SAT problems with the other (at first glance) complexity represented by the search for independent sets and vertex coverings in graphs, namely: we show that 3-SAT ≤P Independent set. The main difficulty in such proofs is obvious: in the 3-SAT problem we are talking about assigning values to Boolean variables taking into account restrictions, while the independent set problem is aimed at choosing vertices in the graph. In order to solve an instance of the 3-SAT problem using the “black box” for the independent set problem, it is necessary to somehow encode all these Boolean constraints in the nodes and edges of the graph so that the fulfillment criterion corresponds to the existence of a large independent set.
This technique demonstrates the general principle of designing complex information Y ≤PX: constructing “controllers” from components in task X to represent what happens in problem Y.
(8.8) 3-SAT ≤P An independent set.
Proof . There is a black box for the independent set problem; we want to solve an instance of the 3-SAT problem, consisting of the variables X = {x1, ..., xn} and conditions C1, ..., Ck.
To correctly look at the problem of mixing, it should be understood that there are two conceptually different points of view on the instance of 3-SAT.
- The first way of representing an instance of 3-SAT was proposed earlier: for each of n variables, an independent decision 0/1 is made, and success is achieved when one of the three ways to fulfill each condition is achieved.
- The same instance of 3-SAT can be represented differently: you need to select one literal from each condition, and then find the logical assignment, as a result of which all these literals give the result 1 with all conditions fulfilled. So, success is achieved if you can choose a literal from each condition so that no two selected literals "conflict"; we say that a conflict of two literals occurs when one is equal to the variable xi and the other to its negation. If conflicts can be avoided, we can find a logical assignment, as a result of which the selected literals from each condition give the result 1.
The following information is based on the second representation of the 3-SAT instance; we will encode it using independent sets in the graph. First, we construct the graph G = (V, E), consisting of 3k nodes grouped into k triangles, as shown in Fig. 8.3. Thus, for i = 1, 2, ..., k, three vertices vi1, vi2, vi3 are constructed, connected to each other by edges. Each vertex is labeled; vij is marked with the jth literal from condition Ci of the 3-SAT instance.
Before proceeding, we consider what independent sets with size k look like on this graph: since two vertices cannot be selected from one triangle, they consist of all methods of choosing one vertex from each triangle. This is how our goal of choosing a literal in each condition is realized, which gives the result 1; but so far we have done nothing to prevent a conflict between the two literals.
Conflicts will be encoded by adding new edges to the graph: we connect each pair of vertices whose labels correspond to conflicting literals with an edge. Will this lead to the annihilation of all independent sets of size k, or does such a set exist? This depends on whether it is possible to select one node from each triangle so that conflicting pairs of nodes are not selected. But it’s exactly what is required in the 3-SAT instance!
It is argued that the original instance of the 3-SAT problem is feasible if and only if the constructed graph G has an independent set with size at least k. First, if a 3-SAT instance is executable, then each triangle in the graph contains at least one node whose label gives the result 1. Let S be the set consisting of one such node in each triangle. The set S is independent; if between two nodes u, v would have to conflict; but this is impossible, since both of them give the result 1.
Conversely, suppose that the graph G contains an independent set S with size at least k. Then, first of all, the size S is exactly k, and it must contain one node from each triangle. It is further argued that there is a logical assignment ν for variables in an instance of 3-SAT, which has the property that the labels of all nodes of S give the result 1. How to construct such an assignment ν? For each variable xi, if neither xi nor is used as a node label in S, we assign ν (xi) = 1. Otherwise, either xi or is a node label in S; because if one node in S were labeled xi and the other, then these two nodes would be connected by an edge, which would contradict our assumption that S is an independent set. If xi is the label of a node in S, we assign ν (xi) = 1;
Since G contains an independent set with a size of at least k if, and only if the original 3-SAT instance was feasible, the reduction is complete.
Link to a review of the book itself here
Now let us give a formal definition to the assignment of values that satisfy a set of conditions. Logical assignment for X is the assignment of a value of 0 or 1 to each xi; in other words, this is the function ν: X → {0,1}. Assignment v implicitly sets the truth value to be opposite to xi. Assignment fulfills condition C if after it C gives result 1 according to the conditions of Boolean logic; this is equivalent to the requirement that at least one of the literals in C has a value of 1. Assignment satisfies the set of conditions C1, ..., Ck if as a result all Ci give the result 1; in other words, if as a result of its conjunction
The logical assignment ν, which sets all three variables to 1, is not fulfilling because the second of the listed conditions is not satisfied; on the other hand, the assignment ν ', which sets all variables to 0, is fulfilling.
Now we can give a statement of the satisfiability problem, also denoted by SAT:
For a given set of conditions C1, ..., Ck with respect to the set of variables X = {x1, ..., xn} is there a logical assignment?
There is a special case of SAT, which has equivalent complexity, but is more clear; all conditions in it contain exactly three literals (corresponding to different variables). We call this task the 3-feasibility problem, or 3-SAT:
For a given set of conditions C1, ..., Ck, each of which has a length of 3, with respect to the set of variables X = {x1, ..., xn}, is there a logical assignment?
The feasibility and 3-feasibility problems are fundamental tasks of combinatorial search; they contain the main components of a complex computational task and in an extremely simplified form. It is required to take n independent decisions (assignment to all xi) so as to fulfill a set of constraints. There are different ways to fulfill each constraint individually, but decisions will have to be combined so that all constraints are met simultaneously.
Reduction of the 3-SAT problem to an independent set problem
Now, we will connect the computational complexity embodied in the SAT and 3-SAT problems with the other (at first glance) complexity represented by the search for independent sets and vertex coverings in graphs, namely: we show that 3-SAT ≤P Independent set. The main difficulty in such proofs is obvious: in the 3-SAT problem we are talking about assigning values to Boolean variables taking into account restrictions, while the independent set problem is aimed at choosing vertices in the graph. In order to solve an instance of the 3-SAT problem using the “black box” for the independent set problem, it is necessary to somehow encode all these Boolean constraints in the nodes and edges of the graph so that the fulfillment criterion corresponds to the existence of a large independent set.
This technique demonstrates the general principle of designing complex information Y ≤PX: constructing “controllers” from components in task X to represent what happens in problem Y.
(8.8) 3-SAT ≤P An independent set.
Proof . There is a black box for the independent set problem; we want to solve an instance of the 3-SAT problem, consisting of the variables X = {x1, ..., xn} and conditions C1, ..., Ck.
To correctly look at the problem of mixing, it should be understood that there are two conceptually different points of view on the instance of 3-SAT.
- The first way of representing an instance of 3-SAT was proposed earlier: for each of n variables, an independent decision 0/1 is made, and success is achieved when one of the three ways to fulfill each condition is achieved.
- The same instance of 3-SAT can be represented differently: you need to select one literal from each condition, and then find the logical assignment, as a result of which all these literals give the result 1 with all conditions fulfilled. So, success is achieved if you can choose a literal from each condition so that no two selected literals "conflict"; we say that a conflict of two literals occurs when one is equal to the variable xi and the other to its negation. If conflicts can be avoided, we can find a logical assignment, as a result of which the selected literals from each condition give the result 1.
The following information is based on the second representation of the 3-SAT instance; we will encode it using independent sets in the graph. First, we construct the graph G = (V, E), consisting of 3k nodes grouped into k triangles, as shown in Fig. 8.3. Thus, for i = 1, 2, ..., k, three vertices vi1, vi2, vi3 are constructed, connected to each other by edges. Each vertex is labeled; vij is marked with the jth literal from condition Ci of the 3-SAT instance.
Before proceeding, we consider what independent sets with size k look like on this graph: since two vertices cannot be selected from one triangle, they consist of all methods of choosing one vertex from each triangle. This is how our goal of choosing a literal in each condition is realized, which gives the result 1; but so far we have done nothing to prevent a conflict between the two literals.
Conflicts will be encoded by adding new edges to the graph: we connect each pair of vertices whose labels correspond to conflicting literals with an edge. Will this lead to the annihilation of all independent sets of size k, or does such a set exist? This depends on whether it is possible to select one node from each triangle so that conflicting pairs of nodes are not selected. But it’s exactly what is required in the 3-SAT instance!
It is argued that the original instance of the 3-SAT problem is feasible if and only if the constructed graph G has an independent set with size at least k. First, if a 3-SAT instance is executable, then each triangle in the graph contains at least one node whose label gives the result 1. Let S be the set consisting of one such node in each triangle. The set S is independent; if between two nodes u, v would have to conflict; but this is impossible, since both of them give the result 1.
Conversely, suppose that the graph G contains an independent set S with size at least k. Then, first of all, the size S is exactly k, and it must contain one node from each triangle. It is further argued that there is a logical assignment ν for variables in an instance of 3-SAT, which has the property that the labels of all nodes of S give the result 1. How to construct such an assignment ν? For each variable xi, if neither xi nor is used as a node label in S, we assign ν (xi) = 1. Otherwise, either xi or is a node label in S; because if one node in S were labeled xi and the other, then these two nodes would be connected by an edge, which would contradict our assumption that S is an independent set. If xi is the label of a node in S, we assign ν (xi) = 1;
Since G contains an independent set with a size of at least k if, and only if the original 3-SAT instance was feasible, the reduction is complete.
Link to a review of the book itself here