A NEW PROOF OF INEQUALITY OF P-NP

Intoduction

The author of this paper presented a first proof of the inequality of the classes of decision problems P and NP in three papers presented to the Academy of Sciences of Turin in 2016 and to the Journal of Computer Science in 2020 and 2022. According to the Journal of Computer Science more than 10000 scientists have read papers and more than 3000 readers have downloaded those papers [1-3].

Two years ago he wrote a new paper. presenting a new version of the first proof, the answers to the questions asked by some readers and the proofs of some theorems which had been omitted for the sake of brevity in the preceding papers. That paper was published by the Journal of Global Research on Computer Science [4]. That paper was copied and became Chapter 2 of the book “Mathematics and Computer Science Contemporary Developments” published by BP International [5].

This paper presents a third proof of the inequality of P-NP, which is absolutely new. It is based on the theory of np-completeness which makes it possible to reduce the length of the proof by many pages.

The starting point. NP-Completeness

P denotes the class of all the decision problems (that is, the problems which have a binary solution TRUE or FALSE) which can be solved in polynomial time.

NP denotes the class of all the decision problems satisfying the property that the function check(f) analyzing a witness of the decision problem is polynomial time decidable.

“P=NP?”, or, in other terms, “Is P a proper subset of NP?”, is one of the most important open questions in computational complexity theory. It is the question discussed in this paper.

According to the theory of np-completeness (which can be analyzed in detail on “NP – Completeness Wikipedia”), a decision problem C in NP is NP-complete if it is in NP and if every other problem L in NP is reducible to it, in the sense that there is a polynomial time algorithm which transforms all and only the instances of L into instances of C producing the same output values [6-16].

The importance of NP-completeness derives from the fact that, if we find a polynomial time algorithm for just one NP-complete problem, then we can construct polynomial time algorithms for all the problems in NP and, conversely, if any single NP-complete problem does not have a polynomial time algorithm, then no NP-complete problem has a polynomial time solution.

The analysis discussed in this paper will be based on the following well-known NP-complete problem which is called “satisfiability problem” or “SAT”.

Given a Boolean expression containing the names of variables (some of which may be complemented), the operators AND, OR and NOT, and parentheses, is there an assignment of TRUE or FALSE values to the variables which makes the entire expression TRUE?

It is well known that the problem remains NP-complete also when all the expressions are written in “conjunctive normal form” with 3 variables per clause (problem 3SAT). In this case, the analyzed expressions will be of the type:

3SAT(t) =

(x₁₁ OR x₁₂ OR x₁₃) AND

(x₂₁ OR x₂₂ OR x₂₃) AND Eq. (1)

………………………

(x_t1 OR x_t2 OR x_t3)

where:

t is the number of clauses or triplets;

every literal x_ij is a variable in complemented or uncomplemented form; every variable may appear multiple times in that expression.

The synthesis of the state of art of question PvsNP can be found [6,7].

The computation of satisfiability problem described by Eq. (1) can be decomposed into two processing layers called “compatibility layer” and “core layer”.

Compatibility layer

A variable j of triplet i will be defined as “compatible” with variable k of triplet h when, and only when, either

• the sign s_ij of the former variable is equal to the sign s_hk of the latter variable,

or

• the binary code <n_ij1 n_ij2 … n_ijm> of the name of the former variable is different from the binary code <n_hk1 n_hk2 …n_hkm> of the name of the latter variable.

From that definition it follows that two “not compatible” variables have different signs and the same name; therefore, there AND is identically FALSE.

The compatibility layer is composed of 3∙t∙(3∙t-3)/2=9∙t∙(t-1)/2 identical operations, one for each pair of variables belonging to different triplets.

The input variables of one of these operations will be the sign sij and the binary code <nij1 nij2 …nijm> of the name of variable j of triplet i, and the sign shk and the binary code <nhk1 nhk2 …nhkm> of the name of variable k of triplet h. The output variable of this operation c(i,j;h,k) will be TRUE when, and only when, the two input variables are mutually compatible.

Therefore, the function implemented by one of the operations of compatibility layer may be written as follows (by using the symbols *, +, and ! for representing AND, OR and NOT operators, respectively):

c(i,j;h,k)=sij*shk+!sij*!shk+
+ nij1*!nhk1+!nij1*nhk1+
+ nij2*!nhk2+!nij2*nhk2+
………………………… Eq. (2)
+nijm*!nhkm +!nijm*nhkm

The value c(i,j;h,k) described by Eq. (2) will be called a “compatibility variable” or simply a “compatibility”.

Core layer

The core layer processes only the 9∙t∙(t-1)/2 compatibility variables c(i,j;h,k) and produces the global result of computation. The Boolean function implemented by the core layer will be called the “Core Function” of order t, where t is the number of triplets. It will be denoted with the symbol CF(t) (or CF(n)). (Indeed, the number t of triplets appearing in Eq. (1) plays the role of symbol n used in the standard complexity theory. In the following analysis, we shall use the symbol t when it is necessary to remember the number of triplets and n in the other cases). The Core Function can be computed by proceeding as follows.

Consider one selection of variables xij appearing in Eq. (1), one and only one for each triplet, for all the triplets. Let

<1 i1>, <2 i2>, …,<t it> Eq. (3)

with i1, i2, …., it ∈ {1, 2, 3}

be the indexes <number of triplet, number of the variable in the triplet> of a selection.

As an example, consider the following satisfiability equation

3SAT(3) =
(x11 OR x12 OR x13) AND
(x21 OR x22 OR x23) AND
(x31 OR x32 OR x33)

The considered selection may be one of the following 27 selections.

Sel1 x11 x21 x31
Sel2 x11 x21 x32
Sel3 x11 x21 x33
Sel4 x11 x22 x31
Sel5 x11 x22 x32
· · · · · · · · · · ·
Sel27 x13 x23 x33

Consider the product of all the compatibility variables relative to the k-th selection:

Φ_k=c(1 i1;2,i2)*c(1 i1;3,i3) * … Eq. (4)

For example, in the case of the above defined 3SAT(27) and Sel 5

Φ₅=c(1,1;2,2)*c(1,1;3,2)*c(2,2;3,2)

The Core Function can be defined as the sum

ΣΦ_k Eq. (5)

of all the products as the one described by Eq. (4) relative to all the selections specified by Eq. (3).

For example, in the case of CF(3) and CF(4), the Core Function can be defined as follows:

CF(3)=                                                                            Eq. (6)
c(1,1;2,1)*c(1,1;3,1)*c(2,1;3,1)+
c(1,1;2,1)*c(1,1;3,2)*c(2,1;3,2)+
c(1,1;2,1)*c(1,1;3,3)*c(2,1;3,3)+
c(1,1;2,2)*c(1,1;3,1)*c(2,2;3,1)+
… (other 22 products) ... +
c(1,3;2,3)*c(1,3;3,3)*c(2,3;3,3)

CF(4)=                                                                                                                  Eq. (7)
c(1,1;2,1)*c(1,1;3,1)*c(1,1;4,1)*c(2,1;3,1)*c(2,1;4,1)*c(3,1;4,1)+
c(1,1;2,1)*c(1,1;3,1)*c(1,1;4,2)*c(2,1;3,1)*c(2,1;4,2)*c(3,1;4,2)+
c(1,1;2,1)*c(1,1;3,1)*c(1,1;4,3)*c(2,1;3,1)*c(2,1;4,3)*c(3,1;4,3)+
c(1,1;2,1)*c(1,1;3,2)*c(1,1;4,1)*c(2,1;3,2)*c(2,1;4,1)*c(3,2;4,1)+
… (other 76 products) … +
c(1,3;2,3)*c(1,3;3,3)*c(1,3;4,3)*c(2,3;3,3)*c(2,3;4,3)*c(3,3;4,3)

It is easy to prove that there is an assignment of values TRUE or FALSE to variables appearing in Eq. (1) which makes the value of that equation equal to TRUE when, and only when, the Core Function takes the value TRUE.

Indeed, for example, if 3SAT(3) is TRUE by virtue of the following equations :

x11=NOT(v1)
x22=v2
x32=NOT(v3)

and

v1=FALSE
v2=TRUE
v3=FALSE

(where v1, v2, v3 are names of Boolean variables), then

c(1,1;2,2)*c(1,1;3,2)*c(2,2;3,2)=TRUE

and, therefore,

CF(3)=TRUE

The reverse is nearly obvious. Assume that CF(3)=TRUE because c(1,1;2,2)*c(1,1;3,2)*c(2,2;3,2)=TRUE. It follows that variables x11, x22, x32 are compatible with each other and, therefore, it is sufficient to assign the right values TRUE or FALSE to the Boolean variables appearing in their definition to obtain that all the variables x11, x22, x32 are equal to TRUE and also satisfiability equation is equal to TRUE.

Notice that the processing work of the elementary operations of compatibility layer (Eq. (2)) increases as a logarithmic function P(t) of the number of the variables since the increment of the length of the code of a name is logarithmic. Therefore, the total processing work of the compatibility layer increases polynomially as 9∙t∙(t–1)∙P(t)/2 where 9∙t∙(t–1)/2 is the total number of compatibility operations.

Besides, the problem solved by the core layer is clearly in NP, because it is easy to verify a witness solution. It follows that, since the compatibility layer polynomially reduces an NP-complete problem (3SAT) to the problem solved by the core layer, the Core Function describes a new NP-complete problem.

Some properties of Core Function have been discussed [9].

Notice that every product of compatibilities of CF(3) or CF(4) appearing in Eq. (6) or Eq. (7) is a prime implicant of the above described Boolean functions. A prime implicant of a Boolean function is a product of variables characterized by the following properties: a) it implies the considered Boolean function; b) the product of any subset of its variables does not imply the Boolean function. Prime implicants play a basic role in the design of Boolean functions as is shown, for example, by the well-known [13].

Completely specified core function

The Boolean function implemented by the core layer, that is, the Boolean function that has been called Core Function CF(n) (or CF(t)), can be viewed as an incompletely specified function.

Indeed, assume that

c(i,j;l,m)=0

and

c(i,j;p,q)=0

This implies that variable <i,j> and variable <l,m> have the same name and a different sign; similarly, <i,j> and <p,q> have the same name and a different sign. It follows that <l,m> and <p,q> have the same name and the same sign. Therefore, c(l,m;p,q) cannot be equal to 0.

Therefore, all the minterms implying

!c(i,j;l,m) * !c(i,j;p,q) * !c(l,m;p,q)

are incomplete specifications of the Boolean function implemented by the core layer. (An incompletely specified function is characterized by a third type of minterms in addition to the two types of minterms defined as TRUE or FALSE. The minterms of this third type are defined as FREE. In the synthesis process a minterm of the type FREE can be freely used as TRUE or FALSE depending on the needs of the design).

It is easy to transform the incompletely specified Core Function CF(n) into a corresponding completely specified Core Function CSCF(n). This result can be obtained by assuming CSCF(n)=0 for all the minterms of CF(n) which are incompletely specified [1].

The result of Meo AR, et al., is the sum of many products of “positive” (or not complemented) compatibilities (PoPC). In this sum a PoPC A may imply a PoPC B; if this occurs, A can be deleted. All the remaining PoPC’s are prime implicants of CSCF(3).

PROPERTY 4.1

Let P₁ and P₂ be two PoC’s such that P₁*P₂ is equal to a prime implicant P of Core Function. It is easy to prove that either P₁ or P₂ is a mark of P (or both of them are marks).

PROPERTY 4.2

Theoretically, the product of a mark M₁ of the prime implicant I₁ by a mark M₂ of the prime implicant P₂ may be equal to I₁*I₂. For example, if

M₁=c(1,1;2,1)*c(1,1;3,1)*c(1,1;4,1)*c(2,1;3,1)

and

M₂=c(1,2;2,1)*c(1,2;3,1)*c(1,2;4,1)*c(2,1;4,1)*c(3,1;4,1)

then

M₁*M₂= I₁*I₂

However, it is easy to verify that M₁*M₂ is implied by (1/8) of the minterms of I₁ and by (1/8) of the minterms of I₂.

In general terms, it is easy to prove for CF(n) that, If M₁ is a mark of prime implicant I₁ and M₂ is a mark of prime implicant I₂, M₁*M₂ can be implied by (1/2^n-1) of the minterms of I₁ and by (1/2^n-1) of the minterms of I₂.

The mark M₁ of prime implicant I₁, multiplied by a mark M₂ of prime implicant I₂, can produce a single prime implicant I₁. This prime implicant I₁ is spurious for at least one compatibility.

For example, the mark of CF(4) M₁=c(1,1;2,1)*c(1,1;3,1)*c(1,1;4,1) of prime implicant I₁=M₁*c(2,1;3,1)*c(2,1;4,1)*c(3,1;4,1), multiplied by mark M₂=c(1,2;2,1)*c(2,1;,3,1)*c(2,1;4,1)*c(3,1;4,1), produces prime implicant I=c(1,1;2,1)*c(1,1;3,1)*c(1,1;4,1)*c(1,2;2,1)*c(2,1;3,1)*c(2,1;4,1)*c(3,1;4,1), which is spurious for compatibility c(1,2;2,1).

Obviously, as already stated, the product of a weak mark M₁ of prime implicant I₁ by a weak mark M₂ of I₁ can be equal to I₁.

PROPERTY 4.2 makes reference to borderline examples. It is extended by the following analysis.

PROPERTY 4.3

The product of two marks M₁ and M₂ which are implied by two different prime implicants I₁ and I₂ of Core Function does not imply Core Function and it is not implied by Core Function. The proof of this PROPERTY is presented in Appendix 3.

PROPERTY 4.4

The best way to integrate operations OR and AND is suggested by the ability of a remainder R to produce 3^m prime implicants (where m is the number of triplet indexes missing in R), through the multiplication by a suitable OoM (“Or of Marks”). For example, the remainder R=c(2,1;3,1) of CF(4), multiplied by nine different strong marks, can be used to obtain the following prime implicants of CF(4):

R*OoM =                                                                                                  Eq. (10)

c(1,1;2,1)*c(1,1;3,1)*c(1,1;4,1)*c(2,1;3,1)*c(2,1;4,1)*c(3,1;4,1) +
c(1,2;2,1)*c(1,2;3,1)*c(1,2;4,1)*c(2,1;3,1)*c(2,1;4,1)*c(3,1;4,1) +
c(1,3;2,1)*c(1,3;3,1)*c(1,3;4,1)*c(2,1;3,1)*c(2,1;4,1)*c(3,1;4,1) +
c(1,1;2,1)*c(1,1;3,1)*c(1,1;4,2)*c(2,1;3,1)*c(2,1;4,2)*c(3,1;4,2) +
c(1,2;2,1)*c(1,2;3,1)*c(1,2;4,2)*c(2,1;3,1)*c(2,1;4,2)*c(3,1;4,2) +
c(1,3;2,1)*c(1,3;3,1)*c(1,3;4,2)*c(2,1;3,1)*c(2,1;4,2)*c(3,1;4,2) +
c(1,1;2,1)*c(1,1;3,1)*c(1,1;4,3)*c(2,1;3,1)*c(2,1;4,3)*c(3,1;4,3) +
c(1,2;2,1)*c(1,2;3,1)*c(1,2;4,3)*c(2,1;3,1)*c(2,1;4,3)*c(3,1;4,3) +
c(1,3;2,1)*c(1,3;3,1)*c(1,3;4,3)*c(2,1;3,1)*c(2,1;4,3)*c(3,1;4,3)

The last gate of CF(n)

For the sake of simplicity, we merely consider the case of CF(n), but the same conclusions also apply to CSCF(n).

Assume that the last gate of the circuit implementing Core Function is an AND gate.

Some inputs of this gate may be the outputs of other AND gates and also the inputs of these gates may be the outputs of other AND gates. The subnetwork of all these AND gates is equivalent to a single AND gate whose inputs are the outputs of OR gates.

Since the output of this AND gate is CF and its i-th input must be equal to (CF + a_i), the output of the gate will be

((CF+a₁)*(CF+a₂)* …*(CF+a_i)*…)=(CF+a₁*a₂* … *a_i …)

where (a₁*a₂*… a_i…) is equal to 0

The cost - that is, the number of AND and OR gates - of the subnetwork producing (CF + a_i) may be less than the cost of the subnetwork producing CF because of the reduction of the number of prime implicants, but the cost of another (CF + a_j) may be equal to or larger than the cost of CF because some complemented variables appearing in a_j increment the number of prime implicants of CF. Therefore, it is not useful to use an AND gate as the last gate of the implementation of Core Function, as shown in Appendix 1.

Therefore, the last gate of the network implementing Core Function must be an OR gate. Some inputs of this gate may be the outputs of other OR gates and also the inputs of these gates may be the outputs of other OR gates. The subnetwork of all the OR gates is equivalent to a single OR gate whose inputs are the outputs of AND gates.

An input I_j of the last OR gate (coinciding with the output of an AND gate) may be: A prime implicant of Core Function (Hp 1);

a PoC implying a prime implicant of Core Function (Hp 2);
a “Remainder And (Or of Marks)”, or “RAOM” (Eq. (10) (Hp 3).
For example, in the case of CF(4), the input of the last AND gate may be:
the prime implicant c(1,1;2,1)*c(1,1;3,1)*c(1,1;4,1)*c(2,1;3,1)*c(2,1;4,1)*c(3,1;4,1); or
the PoC c(1,1;2,1)*c(1,1;3,1)*c(1,1;4,2)*c(2,1;3,1)*c(2,1;4,2)*c(3,1;4,2)*c(1,1;4,3)*c(2,1;4,3); or

the output of the RAOM of Eq. (10).

No other solution is possible as shown in Appendix 2.

The AND gate whose output is a prime implicant of Core Function (Hp 1) or a PoC implying a prime implicant of Core Function (Hp 2) can be defined as a “basic AND gate”. Besides, we can define as a basic AND gate also the AND gate whose output is an input of the OR gate inside the RAOM. Every basic AND gate is useful to produce one and only one prime implicant of Core Function. Therefore, the total number of basic AND gates appearing in the best implementation of Core Function is always equal to, or larger than, the total number of prime implicants of Core Function.

Conclusion

Since the number of AND and OR operations in the best implementation of CF(n) is larger than the number of prime implicants of CF(n) and the number of prime implicants of CF(n) is equal to 3n, it follows that the number of elementary operations necessary to implement CF(n) grows exponentially. Since Core Function is a new NP-complete problem it is possible to state that the classes of decision problems P and NP do not coincide. In brief, it is easy to deduce the names and the signs of variables appearing in the satisfiability equation from the values of compatibilities. If satisfiability equation grew polynomially, also satisfiability equation would grow polynomially. Since it has been proved in this paper that Core Function grows exponentially, also satisfiability equation grows exponentially

References

1. Meo AR. On the P VS NP question: A New proof of inequality. J Comput Sci. 2021;17:511-524.

   [Crossref] [Google Scholar]

2. Meo AR. On a proof of inequality of PvsNP. J Comput Sci.  2023;19:87-98.

   [Crossref]  

3. Meo AR. On the P vs NP question: A proof of inequality. Arxiv preprint.

   [Crossref][Google Scholar]

4. Meo AR. On a proof of inequality of the classes of decision problems P and NP. Glob J Res Comput Sci. 2024;15:003.

   [Crossref]

5. BP International Editor. Mathematics and Computer Science Contemporary Development. 2024;8.

   [Crossref]

6. Fortnow L. The status of the P versus NP problem. Commun ACM. 2009;52:78-86.

   [Crossref][Google Scholar]

7. Carlson J, et al. The millennium prize problems. Amer Math Soc. 2023.

   [Google Scholar]

8. Razborov. Lower bounds on the monotone complexity of some Boolean functions. InSoviet Math Dokl. 1985;31:485-493.

   [Google Scholar]

9. Meo AR. Some theorems concerning the core function. Springer. 2008.

   [Crossref][Google Scholar]

10. Cook SA. The complexity of theorem proving procedures. ACM Press. 2023;143-152.

    [Crossref][Google Scholar]

11. Mulmuley KD, et al. Geometric complexity theory I: An approach to the P vs. NP and related problems. SIAM Journal on Computing. 2001;31:496-526.

    [Crossref][Google Scholar]

12. Wikipedia: NP-Completeness.
13. Hartmanis J. Computers and intractability: A guide to the theory of np-completeness (michael r. garey and david s. johnson). Siam Review. 1982;24:90.

    [Crossref][Google Scholar]

14. Karlsson R. Lecture 8: NP-complete problems. Comput Sci. 2009.
15. Sun HM. The theory of NP-completeness. Wikipedia.
16. Quine WV. The problem of simplifying truth functions. Am Math Mon. 1952;59:521-531.

    [Crossref][Google Scholar]