Views 
   PDF Download PDF Downloads: 1193

 Open Access -   Download full article: 

Approach to Solving K-Sat Problem Based on Reduction Thereof to the Covering Problem

S. V. Listrovoy1 and А. V. Sidorenko2

1Doctor of Engineering Science, professor in the Ukrainian State Academy of Railway Transport (61050, 7, Feuerbach square, Kharkov, Ukraine

2Principal Software Engineer of “Stalenergo” Scientific-Production Enterprise (61105, 9, Fedorenko St., Kharkov, Ukraine

Article Publishing History
Article Received on :
Article Accepted on :
Article Published : 14 Jan 2016
Article Metrics
ABSTRACT:

We propose an exact polynomial-time algorithm for solving SAT the problem.

KEYWORDS: SAT problem; polynomial reducibility

Copy the following to cite this article:

Listrovoy S. V, Sidorenko A. V. Semantic Web: Approach to Solving K-Sat Problem Based on Reduction Thereof to the Covering Problem. Orient.J. Comp. Sci. and Technol;8(3)


Copy the following to cite this URL:

Listrovoy S. V, Sidorenko A. V. Semantic Web: Approach to Solving K-Sat Problem Based on Reduction Thereof to the Covering Problem. Orient. J. Comp. Sci. and Technol;8(3). Available from: http://www.computerscijournal.org/?p=3099


Introduction

SAT-problem is important in systems of evidence automatic verification, where formula is a set of clauses, which mean disjunction of a certain amount of literals – variables Х and X. This problem has a great importance upon determination of satisfiability of CIRCUIT-SAT schemes (circuit-satisfiability problem) and in pattern recognition problems. The international annual conference (The International Conference on Theory and Applications of Satisfiability Testing) that has been held every year for more than ten years, as well as a (Journal on Satisfiability, Boolean Modeling and Computation) are devoted to this problem. An important place in the study of SAT-problem takes design of programs to address them; such programs are called SAT-solvers. Modern SAT-solvers are able to quickly solve many problems that were considered not solved a few years ago. There are many exponential algorithms of its solving and heuristic approaches of polynomial complexity. Among them one should mention the Monien and Shpikermayer algorithm, 1985, in which a simple search is used for solving 3-SAT problem: alternate substitution of each variable with 1 or 0 is tried and then problem of a smaller size is recursively solved; it has temporal complexity О(1,84n) and algorithm for problem of propositional satisfiability of formulas in conjunctive normal form with the complexity of О(1,074n), obtained by Hirsch in 2000. In general, there are two main types of algorithms for solving SAT problems: local search algorithms that start with a certain set of values (though, it does not satisfy all the formula), and then modify it trying to consistently get closer to performed set, and so-called DPLL-algorithms (by names of inventors: Davis, Putnam, Logemann, Loveland; description of basic principles of this method dates back to 1968), which traverse a tree of all possible sets and perform depth-first search. The purpose of this paper is to develop efficient exact algorithm for solving 3-SAT-problem and an arbitrary k-SAT-problem of polynomial complexity.

Formalization of SAT problem and its solution

Let’s consider Boolean function f(X1,X2,..Xn)  in conjunctive form

Formula

 

Operations Ú, Ù are Boolean and simulate simple logic statements: Ú– “OR”; Ù– “AND”. For any binary set X=(X1,X2,..Xnthe function takes one of two possible values: one or zero. The problem “satisfiability” is the answer to the question: whether there is a set of variables x=(x1,x2,..xn), reversing function f into one.

As shown in [1] SAT problem can be considered as covering problem, for this let’s construct by Boolean function a Boolean matrix B in which columns correspond to variables (X1,X2,..Xn) and (x1, x2,..xn), and rows correspond to disjunctions of the Boolean function. In general, the number of columns in matrix В is equal to 2n, and the number of rows is equal to the number of disjunctions m in the Boolean function.

For example, for Boolean function

Formula

Let’s numerate disjunctions of the Boolean function, see Table 1.

Numeration of disjunctions Table 1

Table 1 Table 1 

Click here to View table

 

Then, matrix B will have the form (2)

Formula

 

Columns corresponding to the variables  Xℵ Xin the matrix will be called inverse. If in matrix B there is a covering of rows by units belonging to non-inverse column, it means that f function is satisfiable, if there is no such covering, it is unsatisfiable. Let’s denote variables X—i by Zi, then matrix В, for the Boolean function (1), takes the form

Formula

 

Where if Xi = 1, then Zi = 0 and if Xi = 0, then Zi = 1

As shown in [1], the problem of minimum coverage for any matrix B defined by some Boolean function 

Formula

 

Can be considered as a problem of finding a minimum set of variables {Xi = 1}, where the Boolean function (1) is satisfiable. That can be written in the following form

Formula

 

If we go to the dual Boolean function we’ll obtain

Formula

 

From (7-8) it follows that the problem of the least coverage can be considered non-linear Boolean programming problem that means finding of the smallest number of variables  turning into zero the left side of the constraint (8). If we are talking about the existence of at least one covering, then it is necessary to find out whether there is at least one set of variables  turning into zero the left side of the constraint (8). For the matrix B, defined by correlation (3), condition for the existence of at least one covering will have the form 

Formula

 

Thus, to establish the satisfiability of the Boolean function, we need to show the presence of at least one covering of rows by units in the matrix B, defining a given Boolean function, defined by correlation (3) that satisfies condition (10). For this, it is necessary to solve non-linear Boolean equation (9) and therewith, solution of this equation should satisfy condition (10). If we denote an arbitrary summand by , and the number of summands by m, then the problem (9-10) can be written as

Formula

 

In order to solve problems (11-12), variables of the Boolean function xiσ, taking values Xi , and Zi we’ll characterize by weight characteristics hix and hzi showing the frequency of appearance of variables Xi and Zi in summands of equation (11).

In solving the problem (11-12) for the conversion of some Boolean function we F× in Fx+1 mean a change in the function Fx  by substituting in it pairs, Xj = 1, Zj = 0 or Xj = 0, Zj =1, and since as a result of substitution Xj = 1 or Zj = 1 appeared clauses with fewer variables, We will produce the absorption type of operation XZ V X = X. If the result of substituting in it pairs, Xj = 1, Zj = 0 or Xj = 0, Zj =1 1, it follows that the equality Xj + Zj = 0, t.e. ravening (11) takes the form 1 = 0, then we say that there was a contradiction and the function Fx “not feasible” . If the conversion process appears clauses, consisting of one variable, these variables are assumed to be zero, and enter them in the decision.

The basic idea of ​​the solution of equation (11) is the choice of a clauses  in the original in the original Boolean function F, and is it possible to reset all the other terms in (11) due to the fact that we assume to be zero in turn variables belonging to the selected clauses in this form some intermediate functions in which, too, will allocate clauses and try to reset all the terms in these functions on the basis of a clause in the selection of one of these functions and setting variables in the selected clauses of turn zero. This process continues until we get the identity 0=0 or , proceed to the contradiction 1= 0. In the first case of the function is feasible, and the second is not feasible. In general, the whole set of functions  formed on the basis of one clauses  selected in the initial Boolean function Fx can be represented as a tree, see the following. Figure 1.

Figure 1

Figure 1 

Click here to View figure

 

In Figure 1. shows a tree of all Fx, who will have to build for the solution of «kSAT» for k = 5. To construct the procedure of forming wood  introduce the following notation: Si(r) on the r– level in the tree; Xj(r)is a variable in a number of clauses. In view of the above notation, consider the following 

procedure A, the definition of the solution of (11) with the conditions (12) for the solution of «kSAT» problem, i.e., the feasibility of a task in which each contain clauses on k-variables.

Procedure А

Step 1. Select the equation (11) a clause Si(r) with a minimum number of variables and with the greatest total weight Pr, characteristics choose a variable xj(r) in it with the highest frequency hj (this corresponds to the zero level r = 0) and move on to the next step.

Step 2. Assign a variable xj(r), selected clauses Si(r) zero, and convert a Boolean function Fr to function Fr +1 and proceed to the next step

Step3. Check function Fr +1 “not feasible” and whether there is a disjoint Si(r) variables that are not considered to be zero (ie. check of the conversion process does not result in a contradiction of the form Xi +Zi = 0) If yes, proceed to step 2, otherwise the next step.

Step 3: Check the function Fr +1  of “not feasible”, and whether there is a disjoint  Si(r) variables that were assumed to be zero (i.e. Check the conversion process functions Fr To Fr +1 does not lead to a contradiction of the form Xi +Z= 0)If yes, proceed to Step 2, otherwise the case in the next step.

Step 4. Check the function Fr +1 “feasible” or not (i.e. identity is performed 0=0 in equation (11)), and if so then the algorithm terminates because of the function is feasible, otherwise the next step.

Step 5. Check the function Fr +1 of “not feasible”, that is a contradiction of the form Xi +Zi  =0 when trying to function Fr +1 in zero if the function is turned to zero and thus no contradiction, then go to the next step if the controversy arose, that is, the function Fr +1 “not feasible”, then go to step 7.

Step 6. Go to the next level to find this clause Si(r) with a minimum number of variables and with the greatest total weight Pr characteristics select it in the variable xi(r) with the highest frequency hj in the Boolean function Fr  in the Boolean function

Step 7. Checking were tested at zero (r = 0), all variables on the ability to reset clauses in equation (11), if yes, then the algorithm terminates, since the function “not feasible” otherwise the next step.

Step 8. Back to the previous (r-1) level branching and go to step 2.

The block diagram of this algorithm is presented in Fig.2. Let’s show that procedure A, oriented at solving of k-SAT problem, allows determination for polynomial time whether there is a set of variables in equation (11) allowing turning this equation into an identity upon fulfillment of condition (12). If in equation (11) we take arbitrary summand  Si = X Zb…Xk, it is clear that in order to make Si = 0 and fulfill condition (12) one of k pairs of equalities  X =0, Z= 1; Zb =0, Xb =1;.. Xk =0, Zk =1 should be fulfilled, i.e. in the set of variables of problem (11-12) solution there is one of these pairs and procedure A alternately checks which of these pairs belong to the solution. When we choose a clause Si(r) in original Boolean function F procedure A does not analyze the entire original Boolean function F, and only that part of clauses which crosses the variables selected clauses. Sequences clauses of Boolean functions, which do not intersect the 

Fig.2. The block diagram of an implementation procedure A.

Figure 2: The block diagram of an implementation procedure A.

 
Click here to View figure

 

variables included in the clauses that make up the sequence, they will be referred to independent sequences of clauses. It is clear that if a Boolean function is the number of variables is 2n, and the number of variables in each clause is k, the maximum number of such independent sequences cannot exceed the value 2n/k,i.e. in the worst based on the proposed procedure in the original Boolean function need to zero no more 2n/k such sequences and therefore have to analyze no mor 2n/k trees. So appreciate the complexity of the analysis of one such tree. In accordance with the constructed tree, the number of functions F that will have to be converted equal to the total number of nodes at all levels of the analyzed tree.

As can be seen from Fig.1.the number of nodes at level zero will be equal to k at the first level is k(k-1) at the third level k(k-1)(k-2) and etc. And so, the number of nodes at level zero is equal to k ,the second the number of  vertices does not exceed k2 ,will not exceed kthe third and the last level will not exceed kk-1Consider the amount k+k2+k3+k+…+kk-1 of clear that it cannot exceed the value kk. For example, for the task “3-SAT” in the tree will have to be converted in the worst case k+ k(k-1)+ k(k-1)(k-2)=15 =3+3(3-1)+3(3-1)(3-2)=15 functions. Given that the solution to “k-SAT” problem have to analyze 2n/k trees, in the worst case will have to convert  2kk-1n functions Fr. In the case of a decision “3-SAT” problem, this number will not exceed the amount 15.2n/3 = 10n. For the analysis of the original equations and arbitrary Boolean functions in accordance with the proposed А procedure u need different operations. The number u is determined 2mn a comparison operation to determine the frequency of occurrence of each variable in the selected term and other terms plus  m∙k operations of addition to determine the total value weight Pi of each term in equation (11) and plus Mlog2n operations comparison of the maximum element in the array of m elements, i.e. u = 2mn +mk +mlogm.In the worst case at each step of the procedure A will be reset to zero only one summand i.e. in equation (11) after the first step will remain m-1 summand further m-2, m-3,…,1 summands ,i.e. zeroing all components of the procedures A in the worst case will require completion m(m+1)/2u operations.

Thus, time complexity of work of the proposed procedure A does not exceed 

 Formula

In the case of a decision “3-SAT” problem the number of elementary operations in the worst case may not exceed

Formula

It is known that “k-SAT” problem can be reduced to “3-SAT” problem in polynomial time, in particular in [9] it is shown that if the clause contains more than three literals

Formula

it can be replaced  by ( k-2) clause

Formual

where  new variables, with this new set of clauses satisfied if and only if the following clause. Thus the transition from “k-SAT” problem to a “3-SAT” each clause “k-SAT” problem increases the number of variables in Boolean functions on (k-3), and the number of clauses are restricted to (k-2) clause, and therefore, when the number of variables and clause in a new task will be respectively equal.

Substituting and as new values n and m in   (14) we obtain an estimate of difficulty with this approach to the solution of «k-SAT» task using the procedure A

Formula

Proposed procedure for solving «k-SAT» problem is formally polynomial algorithm but with a high degree of the polynomial (13) and consequently implemented in exponential time, with the solution of the «3-SAT» A procedure performs tasks in polynomial time. Thus, the transformation «k-SAT» problem in polynomial time in the «3-SAT» problem leads to an algorithm of polynomial complexity.

In solving «k-SAT» task using the procedure _ without reducing it to “3-SAT» problem we have exponential complexity of the algorithm and the choice at each step of the procedure A  disjuncts Si(r) 

with the minimum number of variables and with the greatest total weight characteristics can significantly to reduce the average time of the algorithm, by resetting the maximum number of terms in each step of the procedure. Thus, the procedure A is a complete listing of options, may be reset clauses in the case of feasibility reset function occurs in polynomial time, and in the case of “not feasible” function after attempts to reset either the first or the m clauses it turns out that it can not reset and still going strong screening the number of functions in the tree that must be analyzed and this leads to the fact that the average procedure A decides «k-SAT» problem in polynomial time.

Let’s consider examples of work of the procedure A, upon determination of satisfiability of Boolean functions. Let it be required to determine satisfiability of the following Boolean function with four variables and thirteen disjunctions while we assume that the + sign is a sign of logical addition.

f(x) = (x1+x0+x3)(x1+x0+x2)(x0+x3+x2)(x3+x2+x1)(x1+x0+x3)(x1+x0+x2)∙        

∙(x3+x0+x2)(x1+x2+x0)(x0+ x3+ x2)(x2+ x1+x0)(x0+x3+x1)(x3+x1+x2)(x0+x2+x3)                      (18)

Let’s write initial equation

Z1Z0Z3 + x1x0x2 + Z0Z3Z2 + Z3 Z2x1 + x1x0x3 + Z1Z0x2+ Z3x0x2 + Z1Z2x0 + Z0x3x2 + Z2x1x0 +

+ Z0Z3x1 + Z3x1x2 + Z0Z2x3=0;                                                                                                       (19)

We determine frequencies hxof appearance of variables in each summand, see table 2

Formula

 

Let’s choose summand with Z0Z3x1 maximum value of sum of frequencies  equal to 6+6+5=17 and assume Z0=0; x0=1, thus initial equation (19) will take the following form

                                        x1x2 + Z3 Z2x1 + x1x3 + Z3x2 + Z1Z2 + Z2x1 + Z3x1x2=0                           (20)

we perform absorption, here x1x2 absorb summand Z3x1x2, and summands Z2x1 and Z3x2 absorb accordingly summands Z3 Z2x1 and Z3x1x2, thus equation (20) will take the following form

Fr=2  =     x1x2 + x1x3 + Z3x2 + Z1Z2 + Z2x1 =0                                                          (21)

Check the function Fr=1   is reversed to zero, i.e. “doable” or not. In this case, the function Fr=1 is not converted to zero, and in the process of transformation functions Fr=0 in contradictions have arisen, therefore, proceed on the next r+1 level.

Again we determine frequencies  hxof appearance of variables in each summand, see table 3.

 Table3

 

Further, among summands containing the minimum number of variables, such summands are x1x2; x1x3; Z3x2; Z1Z2; Z2x1, we choose the summand with the highest weight characteristics р. In accordance with Table 3, weight characteristics of these summands are, respectively, (4, 4, 2, 3, 5), so we choose the summand Z2x1. There variable with the greatest frequency equal to 3 is variable x1, so we assume x1=0; Z1=1. Thus, equation (21) will take the following form          

Fr=2=    Z3x2 + Z2=0                                                                      (22)

Absorption in (22) cannot be done, but there appeared the summand with one variable, therefore, we believe Z2=0; x2=1 and therefore, equation (22) will take the following form 

Z3=0                                                                                (23)

Thus, a set of variables Z0=0; x1=0; Z2=0; Z3=0 or x0  x1  x2  x3 draws equation (19) into the identity and hence is a performing set of variables for the Boolean function (18). Let’s also consider the process of work of procedure A in the case when Boolean function is not satisfiable. Let function be set as follows

F(x)=(x0+x1+x2)(x3+x0+x2)(x0+x3+x2)(x1+x2+x0)(x0+x1+x2)(x3+x1+x0)(x3+x0+x2)∙            

∙ (x0+x2+ x1)(x3+x0+x2)(x3+x0+x1)(x3+x2+x0)(x2+x3+x1)(x1+x2+x3)                               (24)

Let’s write initial equation         

Fr=0 =x0x1Z2+Z3Z0x2+x0Z3x2+x1Z2Z0+Z0Z1x2+x3x1Z0+x3x0Z2+x0Z2Z1+x3x0x2+x3x0x1+x3Z2Z0+

+Z2Z3Z1+x1Z2Z3=0                                                                                                                  (25)

Since we solve 3-SAT problem we have k = 3 and before the start of work of procedure A variable с=1. We determine frequency hxof appearance of variables in each summand (25), see table 4.

 Table4

 

We choose summand with S*1 = x0x1Z2 with maximum value of sum of frequencies  equal to 6+5+6=17, choose variable with maximum value of , this is x0 and assume; x0=0, Z0=1, thus initial equation (25) will take the following form 

Z3x2+x1Z2+Z1x2+x3x1+x3Z2+Z2Z3Z1+x1Z2Z3=0                               (26)

In (26) summand x1Z2 absorb summand x1Z2Z3 and equation (26) will take the following form

Fr=1=  Z3x2+x1Z2+Z1x2+x3x1+x3Z2+Z2Z3Z1=0                                            (27)

The function becomes zero, and when this controversy arose therefore determined the frequency of occurrence of variables in each clause (27) see table 5.

Table

 

In (26) summand with maximum total value of frequency is x1Z2 with total weight equal to 5 and x3Z2, there we choose variable Z2 with maximum weight 3. Further we assume Z2=0, x2=1, as a result (27) will take the following form

Z3+Z1+x3x1=0                                                                         (28)

As in (28) acquisitions cannot be held, and the terms containing one variable, we assume Z3=0, x3=1 and Z1=0, x1=1, and obtain 1=0 i.e. there is a contradiction, so return to the previous level and move on to try to reset clause x1Z2 based on the variable x1, for in this Fr=1 we assume x1 =0, Z1=1 in (28) will receive

= Z3x2+ x2+x3Z2+Z2Z3=0                                         (29)

In (29) x2 absorbs summand Z3x2 and we obtain the following equation

Fr=3= x2+x1Z2+Z2Z1+x1Z2=0                                          (30)

As in (30) appeared, the terms containing one variable, we assume x2 =0,Z2=1 in (30) then we get x1+Z1=0, i.e., there was a contradiction, i.e. reset clause x1Z2 by variables x1 and Z2 without any contradiction is impossible, so back to zero and check whether all variables are checked for the possibility of exempting clause x0x1Z2 . In this case, not tested variables remained the variables x1 and Z2 and thus the variable Z2 has a greater frequency of occurrence in the clause than x1, so we assume Z2=0, x2=1 in this case equation (25) takes the form

Fr=1=  Z3Z0+x0Z3+Z0Z1+x3x1Z0+x3x0+x3x0x1=0                                  (31)

In (31) summand x3x0 absorb summand x3x0x1, and we obtain

Fr=2=Z3Z0+x0Z3+Z0Z1+x3x1Z0+x3x0=0                                               (32)

The function Fr=2 becomes zero, and when this controversy arose therefore determined the frequency hxiof occurrence of variables in each clause (32) see table 6.

 Table6

 

Among the terms with two variables, select the term with the maximum aggregate rate, this term is a term, this term Z3Z0 with a weight characteristic of 5, select it in the variable Z0 with the largest weight to 4 and assume x0 = 1 and Z0 = 0, at the same time (32 ) will have the following form

Z3+x3=0                                                        (33)

i.e. there was a contradiction therefore return to the previous level to zero clause Z3Z0 based variable Z3, for this purpose (32) believe x3 = 1, Z3 = 0, we obtain

Fr=1= Z0Z1+x1Z0+x0=0                                                  (34)

In (34) there was a term consisting of one variable, so assume x0 = 0 and Z0 = 1, and we obtain the Z1 + x1 = 0, i. e. there was a contradiction. Next, check whether all the variables at zero were used to clear the clause x0x1Z2. In this case, we are left with no proven only one variable x1, therefore believe x1 = 0, Z1 = 1, the equation (25) becomes

 

Among the terms with two variables, select the term with the maximum aggregate rate, this term is a term, this term Z3Z0 with a weight characteristic of 5, select it in the variable Z0 with the largest weight to 4 and assume x0 = 1 and Z0 = 0, at the same time (32 ) will have the following form

Z3+x3=0                                                        (33)

i.e. there was a contradiction therefore return to the previous level to zero clause Z3Z0 based variable Z3, for this purpose (32) believe x3 = 1, Z3 = 0, we obtain

Fr=1 Z0Z1+x1Z0+x0=0                                                  (34)

In (34) there was a term consisting of one variable, so assume x0 = 0 and Z0 = 1, and we obtain the Z1 + x1 = 0, i. e. there was a contradiction. Next, check whether all the variables at zero were used to clear the clause x0x1Z2. In this case, we are left with no proven only one variable x1, therefore believe x1 = 0, Z1 = 1, the equation (25) becomes

Fr=1=Z3Z0x2+x0Z3x2+Z0x2+x3x0Z2+x0Z2+x3x0x2+x3Z2Z0+Z2Z3=0                             (35)

After absorption by summand x0Z2 of summand Z3Z0x2 and x3x0Z2 we obtain

Fr=1=x0Z3x2+Z0x2+x0Z2+x3x0x2+x3Z2Z0+Z2Z3=0                        (36)

The function does not vanish, and thus no contradiction, therefore, determines the frequency of appearance of the variables in each of clauses (36) cm. Table 7.

Table7

 

Among the clauses in the two variables (36) Select clause to the maximum aggregate rate, this term is a term with a weight x0Z2 characteristic of 6, select it with the variable x0 frequency of occurrence in other clauses of (36) equal to 3 and suppose x0 = 0 and Z0 = 1, and (36) takes the form

Z3x2+x2+x3Z2+Z2Z3=0                                              (37)

In (37) x2 absorb Z3x2 and we obtain

x2+x3Z2+Z2Z3=0                                                       (38)

In (38) there was a term with one variable x2, so expect x2 = 0 and Z2 = 1 in this case we obtain x3 + Z3 = 0 i.e., a contradiction, so we return to the r-1 level i.e. go to the function defined by (36) and proceed to attempt to reset the clause  x0Z2 based variable Z2, for this purpose (36) believe Z2 = 0, x2 = 1, we get Z3Z0 + x0Z3 + Z0 + x3x0 = 0, having absorption get x0Z3 + Z0 + x3x0 = 0, where there was a term with one variable Z0, therefore believe Z0 = 0, x0 = 1 and obtain Z3 + x3 = 0 i.e., formed a contradiction therefore return to the r-1 level in the case of zero and check instill variables were used to clear the clause x0x1Z2 in this case it was the last variable, and hence the procedure terminates since assuming zero variables in clauses x0x1Z2 pay equation (25) into an identity and therefore can not function (24) is not feasible.

It should be noted that these estimates of time complexity of the procedure A, for the worst case, are pretty rough estimate from above because when it is obtained it was assumed that when assigning X∫ = 0 and Z∫ =1 at each step only one summand is reset to zero, but in fact hxi summands are reset to zero and therefore it is of interest to obtain an estimate of the average work of the procedure A. In the experiment, 2n variables X∫ and Z∫ posted by disjunctions according to uniform distribution law. Results of experimental studies were obtained with a confidence probability of 0.95, while for the average value of the number of elementary operations performed by procedure A at each point from 50 to 70 Boolean functions of studied dimension were generated. Upon experiment the number of disjunctions m ranged from 100 to 10,000, and the number of variables n changed from 90 to 2400, experimental results are shown in tables (8-12). Period of work of procedure Аis given in milliseconds.

Table 8

m = 500; k = 3

n

100

110

120

130

140

150

Number of elementary operations

1.06·108

7.2·108

8.6·109

4.2·108

63,209

52,096

 

0.2

0.22

0.24

0.26

0.28

0.3

Satisfiability

+

+

+

Minimum time of solution – 5.06 ms

Maximum time of solution – 793,934 ms

 

Table 9

m = 500; k = 3

n

400

800

1200

1600

2000

2400

Number of elementary operations

286987

106

2.24·106

4·106

6.2·106

8.9·106

 

1.25

0.625

0.416

0.313

0.25

0.208

Satisfiability

+

+

+

Minimum time of solution – 36.5 ms

Maximum time of solution – 849 ms

 

Table 10

m = 90; k = 3

m

100

200

300

400

500

600

Number of elementary operations

16029

26994

37413

4.39·107

2.42·107

1.86·107

 

0.90

0.4

0.3

0.23

0.18

0.15

Satisfiability

+

+

+

+

Minimum time of solution – 2.15 ms

Maximum time of solution – 38,910 ms

 

Table 11

m = 500; n = 90, α = 18

k

3

10

20

30

40

50

Number of elementary operations

2.42·107

60,807

48,555

55,488

64,268

74,508

 

0.2

0.22

0.24

0.26

0.28

0.3

Satisfiability

+

+

+

+

+

Minimum time of solution – 7.57 ms

Maximum time of solution – 160 ms

 

Table 12

m = 10,000; k = 3

n

100

200

300

400

 

Number of elementary operations

324,459

1.25·106

4.89·106

9.5·107

 

 

0.2

0.22

0.24

0.26

 

Satisfiability

+

 

Minimum time of solution – 44 ms

Maximum time of solution – 819,261 ms

 

Tables (8-12) show that the largest number of operations is made by the procedure at ratios α=n/m close to 0.24, while for a uniform law of distribution of variables X and X  by disjunctions at <0.24 Boolean functions are generally not satisfiable, and at> 0.24 Boolean functions become satisfiable. Sign (+) in tables means that functions are satisfiable, and sign (-) indicates non-satisfiability of Boolean functions. When α is close to 0.24 probability of occurrence of satisfiable and unsatisfiable Boolean functions becomes the same and thus the number of operations fulfilled by procedure A is increased. Thus, in case where Boolean function contained number of disjunctions m = 800 and number of variables n = 200, i.e. α = 0.25, the average number of solution was equal to 1,96 1011, at the upper value equal to 1,6∙1014, and the average time of solution was 4.9 hours. With increasing of k, see. Table 10, where the summand k+log2m/2n in (17) is significantly less than unity, there is a decrease of time complexity of the procedure’s work, due to the increased number of zeroed summands at each step of the procedure’s work. However, upon further increase of the summand, k+log2m/2n when it becomes significantly greater than unity, there is a further increase in the number of elementary operations fulfilled by procedure A. In order to test the developed algorithm we used 900 test of specialized library SAT Live [12] containing 403 disjunctions and 100 variables with the value of parameter α = 0.248 generated by pseudo-random filling of disjunctions. Test results are shown in Table 13.

Table 13

Test name

Number of variables

Number of disjunctions

Average number of fulfilled operations upon solution

Average time of solution in ms

Minimum time of solution in ms

Maximum time of solution in ms

CBS_k3_n100_m403_b0

………………………….

CBS_k3_n100_m403_b900

100

403

51·106

4,578

2.28

77,843

 

Algorithm testing was carried out on a computer ASER with Intel Pentium processor T4400, 2.2Ghz, 3GB Memory.

Summary. Since the issue of existence of an exact polynomial algorithm for solving SAT problem is closely connected with the issue of the relationship of classes P and NP, let’s consider it in more detail.

Today, seven mathematical problems included in the list of millennium tasks are known, one of them is the problem of the relationship of classes P and NP. The issue of the relationship of classes P and NP is now considered one of the main open issues of modern mathematics and theoretical cybernetics. The founders of this problem are Stephen Arthur Cook, Professor from University of Toronto and a Turing Award winner, and Professor Leonid Levin. Cook’s works introduced the concept of NP-complete problems and proved that the problem of “satisfiability” also known as the SAT-problem is universal NP-complete problem. Further development of the theory of NP-complete problems was made by a professor at Harvard University, Richard Manning Karp. In recent times, there have appeared papers of Indian mathematician, Vinet Deolalikar, and article “On the Relationship between Classes P and NP” written by the Ukrainian professor Anatoly D. Plotnikov in Journal of Computer Science 8 (7): 1036-1040, 2012. These papers prove the divergence of these classes. And the paper of Russian professor A. V. Panyukov proves that P = NP. Let’s show the incorrectness of these efforts of evidence on the basis of results already obtained by the authors in [1, 2, 3] and results obtained in papers of Lavrov and Zykov [7, 8, 9], as papers [1, 2] show that SAT-problem is not universal.

It should be noted that the class of NP-complete problems is based on the concept of universal problem. All problems belonging to the class of NP-complete should be universal and polynomially reducible to each other. Therefore, if polynomial algorithm is received for solving some problem I belonging to the class of NP-complete, then in accordance with the Cook’s theorem [4] there should be polynomial solvability of all problems belonging to the class of NP-complete. In [4] Cook argues that the problem “satisfiability” is NP-complete. Once one NP-complete problem has become known, the process of proof of NP-completeness of the problem A is simplified. In order to prove the NP-completeness of the problem АÎNP it is enough to show that any of known NP-complete problems А/ can be reduced to A, since the property of polynomial reducibility is transitive, i.e. if the problem A is converted to the problem B during the polynomial time, and if B is converted to C during the polynomial time, then A will be converted to C during the polynomial time. First this scheme was used to prove NP-completeness of six main problems: “three-dimensional combination”; “partition”; “vertex cover”, “Hamiltonian cycle; “clique”. Since these were the first problems introduced in the class of NP-complete problems after “satisfiability” problem, the proof of their NP-completeness was reduced to introduction of rule П, based on which using some arbitrary problem of “satisfiability” y∈Y there was built structure S, with ν property, if and only if γ possesses the value truly. For example, for the problem of “vertex cover” graph G was as the structure S, and ν property laid in the fact that graph G has a vertex cover with the number of elements not more than K, if and only if the following set of disjunctions C={c1,c2,…cm} defining an arbitrary individual “3-satisfiability” problem, is satisfiable. In general, the problem of “satisfiability” is a set of Y individual problems defined in various ways of defining logic function. It should be noted that when proving NP-completeness of all six listed problems first there was selected an arbitrary individual task y∈Y and it is used for construction during a polynominal time of graph G, having a structure interesting for us with necessary ν property, only if the logic function corresponding to a given individual problem, possesses the value truly. Since graph G can be arbitrary, we solve some individual problem z∈Z , where Z-set of problems generated by using various types of graphs G.

Upon solving any NP-complete problem of graph theory there is an inverse problem: an arbitrary graph G is given, and it is required to set whether this graph G has structure with v property or not.

The following issues arise: what individual task (y) from a set of individual problems “satisfiability” Y corresponds to the problem z∈Z 

generated by graph G, and whether there is inverse for all problems Z or not, and, if so, how it can be constructed according to the original graph and whether such construction is a polynomial or not?

It should be noted that Cook’s evidence of universality of problem “satisfiability” was present a priori and it was not clear whether there is at least one NP-complete problem or not. However, [2, 3, 4] show that “satisfiability” problem cannot claim to be a universal problem, i.e. NP-complete problem. As follows from [2, 3, 4] set of objects that are described by unsatisfiable Boolean functions in an exponential number of times are greater than the number of objects that are described by satisfiable Boolean functions, and properties of polynomial reducibility are by default extended to objects described by unsatisfiable Boolean functions. It was shown in [2, 3] in the vertex cover in graphs. According to [2, 3] it is possible to construct an exponential set of graphs the set of disjunctions ,C={c1,c2,…cm} defining an arbitrary individual problem, of which is unsatisfiable on any set of variables, and hence reduction of the problem of vertex cover to the SAT-problem for these graphs is impossible. It is easy to show that this fact happens for the problem of Hamiltonian cycle in graphs, as well as any other problem in the theory of graphs included in the list of NP-complete problems.

Initially, in the theory of NP-complete problems, there was laid an error associated with the fact that upon proving of NP-completeness the concept of individual problem does not take into account the topology of studied object. Description of any object is defined by some basic subset of elements describing this object and ratio  set on this subset and determining topology of this object, since various ratios  can exist for the object of the same dimension, these relationships set different topologies of this object. Let’s start with the concept of problem. The mass problem means a common issue that should be answered. The problem is defined by the following information:

  • General list of all of its parameters;
  • Formulation of those properties to be satisfied by the solution of the problem.

Individual problem is obtained from the mass one, if specific values are assigned to all parameters of the mass problem, but should be more specific, and upon proving of NP-completeness this fact is simply ignored. For example, upon proving NP-completeness of the problem of Hamiltonian cycle Karp [7] finds a very exotic graph structure for which SAT-problem is satisfiable, if and only if it has a Hamiltonian cycle. Then, there is an issue whether this property will be performed for all structures, and if such Boolean function cannot be constructed for some topologies, on what basis we should include these problems in the class of NP-complete problems. If we take two graphs of the same dimension, but different in topology, for example one of them is perfect and the other is not, then it is clear that the set of problems that we can solve for the perfect graph does not coincide with the set of problems solved on an imperfect graph. But from the standpoint of Karp evidence it does not matter.

Thus, Cook theorem is valid only for objects described by satisfiable Boolean functions. It should be borne in mind that the number of such objects is negligible compared with objects described by unsatisfiable Boolean functions [2, 3]. So we found that SAT-problem is not universal, and limits to applicability of Cook theorem are very limited. Now let us show that the very proof of NP-completeness of the problem requires clarification. For this let’s consider the issue of the proof of NP-completeness of arbitrary problem. As shown in papers [2–7], polynomial reducibility of recognition problem I1to the recognition problem I2 means availability of function f, which is based on some rules Пi represents a subset of problems Di1 in a subset of problems Di2 (Di1 Di2), and thus satisfy fulfillment of two conditions:

f is calculated by polynomial algorithm;

  1. For all I∈ Di I Yд1,when and only when f(I) Yд2,

where Yд  is set of problems with answer “yes”, while Yд Di .

Let’s consider three subsets of problems {Ii}; {Zi}; {Ci}. Let problem I-NP be complete and represent a universal problem, and problems Z and С are also NP-complete, then in accordance with the manner how class of NP-complete problems is introduced, they should be polynomially reduced one to another and, thus, if a polynomial algorithm for one of them is found, there should exist polynomial algorithms for all individual problems {Ii}; {Zi} ;{Ci}. As any of NP-complete problems can be a universal problem, all the following information should be valid:

Formula

Thus, there are rules Пiz and Пzc, allowing to reduce problems Ip Zp and thus, {Iр}∈Yдi and problems Zp→ Cp and thus, {Zр} ∈ Yдz, i.e. rules of conversion of Пiz and Пzc satisfy conditions of polynomial reducibility 1 and 2. Let’s consider the case when S structures are such that generate a set of individual problems {Z}, which by power is greater than the set of individual problems {I}. If the subset {I} contains n individual problems, and sets {Z} and {C} contain n+k individual problems each then, for some subset of problems {Zn+1,Zn+2,…,Zk} we could not assign any problem from {Ii}. Consequently, reduction (39) and (40) is possible for all problems and reductions (41), (42), (43) and (44) are possible not for all problems, they are impossible for problems {Сn+1n+2,…,Сk} and {Zn+1,Zn+2,…,Zk}, and, therefore, in this case, the statement that all NP-complete problems are polynomially reduced to each other is not satisfied. Thus, the concept of NP-complete problem needs clarification. In order to make NP-complete problem universal and reducible in all directions inside the class, it is necessary to have a perfect correspondence between all individual problems {Ii};{Zi};{Ci}, i.e. for any pair of individual problems there should be direct and indirect polynomial reduction determined by conditions 1 and 2.

So, if we have subsets of problems {Ii}; {Zi}; {Ci}, and power of set of individual problems {Ii} is different from power of set of problems {Zi} and {Ci}, then in order to prove that certain problem I is NP-complete, it is not enough to show that any individual problem {Ii} is polynomially reduced to set of problems {Zi} and {Ci}, i.e. conditions 1 and 2 are fulfilled, as upon proving NP-completeness of “satisfiability” problem in papers of Cook and Levin, but in this case it is necessary to show that there are problems {Іn+1n+2,…,Іk}, polynomially reduced to problems {Сn+1n+2,…,Сk} and {Zn+1,Zn+2,…,Zk}, and “checkability” of these problems of recognition should be polynomial.

Papers [2, 3, 4] show that all problems related to class NP-complete can be divided into subsets of problems , inside of which polynomial reducibility is possible and hypothesized that between subsets  apparently there only possible polynomial reduction of certain individual problems. Therefore, here we can talk only about polynomial solvability of individual problems, which can be reduced to a problem I. The only thing that unites problems which we attribute to NP-complete is the fact that no algorithm for solving polynomial complexity is known for them. It is therefore proposed to use for these tasks the term hardest problems instead of the term NP-complete problems. In paper [2] it is hypothesized that the issue of the existence of the universal problem is algorithmically unsolvable problem. As follows from [8, 9, 10], this hypothesis is supported by the fact that now the list of NP-complete problems includes more than three thousand tasks, and thus it includes almost all major problems of the theory of graphs, then proceeding of the declared Cook polynomial reducibility of problems within that class, for solving all problems of graph theory included in this list there should exist an algorithm to solve them with some arbitrarily high complexity, which leads to their polynomial reducible to each other, but this is contrary to results obtained in papers of I. A. Lavrov (1963) [8] which shows the impossibility of construction of such algorithm and to what A. A. Zykov focused attention in papers [10]. 

Conclusions                                                    

  1. The problem of relationship of classes P and NP posed by Cook and ranked in the list of millennium tasks is just ill-posed mathematical problem; therefore, it is not surprising that nobody could solve it. This problem should be excluded from the list of millennium tasks, as to this date scientists are spending their precious time to solve it, it is evidenced by papers of Indian mathematician Vinet Deolalikar and article of Ukrainian Professor A. D. Plotnikov and Russian Professor A. V. Panyukov. The presence of this problem in the list of millennium tasks inhibits further development of mathematics. It should also be noted that the theory of NP-completeness cannot be used to study properties of optimization problems [11], and thus all results obtained in the theory of algorithms, based on the “total” reducibility within the class of NP-complete problems, declared by Cook, require serious revision.
  2. The paper shows that SAT problem belongs to the class P, but that does not mean equality of classes P and NP, but only determines the possibility of solving during polynomial time some subset of problems that are polynomially reducible to SAT-problem and allows to create fast SAT-solvers able to solve many problems of discrete optimization of large dimension in real time, which previously were considered unsolvable.

References

  1. S. V. Listrovoy, Minukhin S. V. Investigation of the Scheduler for Heterogeneous Distributed Computing Systems based on Minimal Cover Method // International Journal of Computer Applications (0975 – 8887) Volume 51 – No.19, August 2012, р 35–44.
  2. Listrovoy S. V. On Correlation of Р And NP Classes // I. J. Modern Education and Computer Science, 2012, 3, 21-27.
  3. Listrovoy S. V. On NP classes and NP-complete problems. // Electronic simulation, 2011, vol. 33, No.1, p. 31–45.
  4. Listrovoy S. V. “On polynomial reducibility in NP class”, Ukrainian Mathematical Congress − 2009, Algebra and Number Theory. http://www.imath.kiev.ua/
  5. Gary М., Johnson D. Computing machines and hard problems. – М: Mir, 1982. – 336 p.
  6. Cook S. А. Complexity of procedures of a conclusion of theorems. – Cybernetic collection of a new series, vol.12. – Moscow.: Mir, 1975.-Р.5 – 15.
  7. Karp R. М. Reducibility of combinational problems. – Cybernetic collection of a new series, vol. 12. – Moscow: Mir, 1975.-Р.16-38.
  8. I. A. Lavrov. Effectiveinseparability of a set of identically true and a set of finitely refutable formulaeof some elementary theories. Algebra and logics (Materials of the workshop of Institute of Computational Mathematics and Mathematical Geophysics of Siberian Branch of the USSR Academy of Sciences) 2 (1963), No.1, 5-18. RzhMath, 1964, 1А112.
  9. Papadimitriou, K. Steiglitz Combinatorial optimization Algorithms and complexity– M.: Mir, 1985.-509p.
  10. A. A. Zykov. Elements of graph theory // Moscow: Nauka, 1987, p. 381.
  11. S. V. Listrovoy. ON THE THEORY OF NP-COMPLETE PROBLEMS // International Journal of Computers & Technology, Vol. 11, No. 4 Oct 20, 2013- Р. 2481–2483.
  12. SAT Live [Digital resource]. – Access mode: www.satlive.org, free.

 


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.