Leonard Gojer, B.S. Computer Science, University of Texas, Dallas, Prateek Swamy, B.S. Computer Science
Abstract – The prior consensus among computer scientists for the past 50 years or more has been that the NP-Complete problems have no polynomial order time solutions. An important part of that existing body of Computer Science theory is that the “Circuit Satisfiability” problem has no polynomial order timesolution. The author here presents a new algorithm for the Circuit Satisfiability problem which can be proven to run in polynomial order time, thereby reversing the consensus of the premise that P<>NP and replacing it with the premise that P=NP.
Keywords: computational complexity, polynomial order time, exponential time, NP-Complete problems
I. INTRODUCTION
The curriculum of modern computer science classifies mathematical algorithms according to their computational complexity, among other characteristics suc as the department of Calculus or Discrete Math that they would reside in, in order to facilitate the activities of researchers who might come across
the algorithms when searching through the science literature. The NP-Complete problems is a class of mathematical optimization problems which have been categorized by computer scientists of the past according to the scientific conclusion that they cannot be solved in polynomial order time. This was originally concluded by Claude Shannon in the 1950’s when he analyzed the BDD algorithm. (X) This label of NP-complete is to warn future computer scientists who might encounter the material that they will not achieve efficiency in implementing the algorithms that are labeled as NP-Complete. And is to encourage those scientists to not consider the NP-Complete solutions to algorithms unless as a worst case solution to the problems at hand, but to instead consider algorithms that are not NP-Complete first in the creative design process of designing a new program. Algorithms in computer science are established by the systematic research of computer scientists who dedicate time to experimenting with the mathematical possibilities that could be constructed in the computer and then recording their findings and theorizing about the complexity of what they have found. The algorithm presented here is an example of the product of such research, which was performed by myself during the years 2000-2005. Consider that in the development of modern mathematics, formulas are recorded in the textbooks when they have been deemed to be worthy of being recorded due to the time savings that they represent when they are used by mathematicians. Many famous theorems in mathematics, such as in the Calculus were originally discovered in the prior centuries and they have been passed down to the students of the present time because they have been found to be continuously useful in modern circumstances, rather than discarding them. This algorithm is worth keeping and using for the same reason, it represents a big savings in time and money for the programmers and computer owners who use it.
There are six categories of problems in the computer science literature that are classified as
NPComplete. They are respectively:
• The Circuit Satisfiability Problem
• The Traveling Salesman Problem
• The Subgraph Isomorphism Problem
• The Graph Coloring Problem
• The Subset Sum Problem
• The Vertex Cover Problem (2)
In “Guide to the Theory of NP-Completeness”, which was originally written in 1971, Gary and Johnson
illustrate the fact that all of these problems are considered transformations of each other in the
theory of computation. The Circuit Satisfiability problem, along with the other variations of NP-Complete
problems, is a problem that in its prima fascia form consists of what is called an “optimization” problem,
which is a type of problem that concerns itself with finding the optimal arrangement of the data to either
maximize a given function of the data items in the problem or minimize it, (depending on what the
circumstances from the real world are). An example of a maximization problem would be to maximize
profits from some economic function. An example of a minimization problem might be to minimize the
material or costs of some project. The significance of finding a polynomial order time solution to the
Circuit Satisfiability problem is that it allows computer software to be created that uses it to solve some
important engineering problems, such as, for example, the design of electrical logic circuits in IC chips
within a time constraint that saves an increasing amount of time and labor as the size of the problem
increases. In this particular example, it allows computer scientists to create very large chips which
dramatically outperform the existing IC chips which represents a very large economic payback for the
electrical engineers when the design is very large. Many people in the past have tried to create polynomial
order time solutions of the Circuit Satisfiability problem and have concluded that the problem has no polynomial
order time solution. They have published their mathematical work in the literature since the 1950’s
to the present. It becomes important in this paper to explain what was done differently in this solution to
facilitate that it works to make the explanation clear.
Today, existing algorithms for solving the Circuit Satisfiability problem are Genetic Algorithms which
apply the concept of Genetic programming in AI. This is because a Brute Force method of solution to the
optimization problem performed without any inspired mathematical knowledge takes an exponential
order running time to perform, (1) this was stated by Claude Shannon in the 1950’s along with Donald
Knuth, who wrote “The Art of Computer Programming”. Genetic algorithms work by the mechanism of
probability theory as it concerns the patterns in the data. An example of a genetic algorithm for solving a
problem might be the following, to create a stock market indicator which would be optimized to the
successful for a long period of time in the historical past. The genetic algorithm would start with an original
hypothesis that was generated randomly and then proceed to revise it over and over again until it passed the
test of some statistical criteria of how close it comes to perfection. Each time that it revised it, it would
utilize the Genetic algorithm paradigm which is a sophisticated method of making good guesses for generating the
next attempt at the solution. The process would halt when the criteria of satisfaction was satisfied.
Existing algorithms for solving the Circuit Satisfiability problem using the Genetic Algorithm approach
thus start with a randomly generated solution which may or not be the final solution, (usually it probably
isn’t) and then refine the solution iteratively using the idea of “good guesses” that are based on the
Genetic Algorithm methodology, which uses the idea of elaborate hypothesis composition formulas.
That means that existing solutions to the SAT problem based on using Genetic algorithms have the
characteristic that most of the time, they probably finish in polynomial order time, but in a few bad
instances, they take exponential time to run. This happens when they reach an inefficient pathway by
mistake, or rather by random chance.
II. RELATED WORK
Most existing work that is prevalent in the computer science literature today either tries to find a better
genetic algorithmic technique for the SAT algorithm or else tries to prove that the P=NP problem cannot
be solved with a polynomial order time solution . A few of these prominent computer scientists agree that
P = NP. A survey of the existing work that was compiled in a web article shows that 50% of the computer
scientists of a group of about 20 computer scientists concluded that P<>NP and the other 50% concluded
that P=NP, providing some very creative arguments on both sides of the issue.
Another example of what is done in the public arena is to have public contests that are run to encourage
people to find better genetic algorithms for the SAT algorithm. For example, there is a contest that is held
regularly on the internet where programmers are invited to try to make faster algorithms for the SAT
algorithm; it is called “SAT Live!” and the contest is held every year with prizes being given away. (4)
Some computer scientists have also taken the P=NP side of the issue and have concluded in a manner
similar to the authors of this paper that P=NP because Integer Linear Programming, (which is one of the
NP-Complete Problems, and which has been shown to be another form of the SAT algorithm), can be
solved in polynomial order time. (3) The TSP can be solved with Integer Linear Programming.
III. OUR RECURSIVE ALGORITHM FOR SAT
The algorithm of this paper is based on a novel use of the idea of recursion with respect to the processing
of binary trees. The idea is to first parse the Boolean expression in question into the form of an Abstract
Syntax Tree, (similar to what happens in the internal mechanism of a compiler, such as the C# compiler
or C++ compiler), and then to process the nodes and leaves of the binary tree according to a process that
is recursive. The recursive property has the characteristic that subtrees can be checked for the question of
whether or not they are SAT, (satisfiable), using the exact same algorithm, and that the question of
whether the total tree is SAT, (satisfiable), is solved by the prior determination of the question of SAT for
the subtrees.
The fundamental proposition of this new algorithm is: P is SAT if either:
- P consists of a a Not (Q) and Q is not SAT
- P consists of an (Q or R), and Q is SAT or R is SAT
- P consists of an (Q and R) and (Q is SAT) and (R is SAT) and the solution of (Q is SAT) is not the
inverse of the solution of (R is SAT). This statement is relatively easy to state in an OOP programming
language such as C++ or C#. What is needed is a function that is called:
Bool isSAT(SATProposition P)
{
Bool tmp = false;
If (isaNot(P)) { tmp = !(restof(P)); }
If (isanOr(P)) { tmp = isSAT(leftPtr(P)) or isSAT(rightPtr(P)); }
If (isanAnd(P)) { tmp = isSAT(leftPtr(P)) and isSAT(rightPtr(P)) and
notInverses(leftPtr(P),rightPtr(P)); }
Return tmp;
}
It becomes relatively trivial to carry out the implementation of the above described algorithm, once it has
been properly stated that way in a programming language, such as C#. (Actually would be better for this coding
project because C# does not allow pointers in the same way that C++ does). It can then be shown that when the SAT
expression is of height 1, that the running time of the algorithm is a k (constant), running time, because
there is no step of recursion.
Next, it can be shown that the running time of the algorithm for cases that are of height greater than 1 is
some composite function of O(n log n), because that is the running time of a process that enumerates the
leaves of the binary tree with recursion. The only thing that remains in the computation of the Big O (running
itme), of the algorithm is to know what the running time of the internal process of the algorithm inside
of that is. The easy cases are close to a constant order. The hard cases are close to the running time of
O(n^2). The reason for that is because the hard cases depend on an internal algorithm called the “Equivalence
Algorithm” which is a subroutine of the notInverse(P1,P2) Algorithm that is used in the solution of
SAT.
The purpose of the “Equivalence Algorithm” is to check if two propositions are the exact same
proposition and return true if they are. This is an important issue in theory of the NP complete problems
because in the prior literature, Equivalence was considered the same isse as the BDD algorithm which
proports that P <> NP, so solving Equivalence in P time is a secondary proof of the thesis of this paper.
That result is used by the notInverse Algorithm in the following manner:
Bool notInverse(SATProposition P1, SATProposition P2)
{
Bool tmp = true;
If (Equivalent(P1,!P2) or Equivalent(!P1,P2))
{
tmp = false;
}
Return tmp;
}
First Attempt at Solution Involved Using Graph Isomorphism
In the first attempted solution of the SAT algorithm, the process of checking to see whether two sub-
Propositions are equivalent involves a complicated algorithm which is based on calling Graph
Isomorphism as a subroutine. First, the two trees of the expressions are rewritten in the form of
graph adjacency matrices. Then, the two adjacency matrices are compared with a graph isomorphism algorithm.
It has been proven in the historical past that graph isomorphism can run in polynomial order time. There
are now many algorithms to choose from. One such algorithm devised and proven in the year 2009 by Ashay
Dharwadker and John-Tagore Tevet is discussed here. There are other algorithms for graph isomorphism in
the computer science literature that run in polynomial order time. I myself devised on in the year 2001
which I think is similar but not identical to the one by Dharwadker and Tevet, but I am going to talk
about theirs, since theirs is more formally proven in the mathematical literature of computer science.
The algorithm works by manipulating the rows of the adjacency matrix until the canonical form is
reached. It is a relatively complex algorithm which for the purpose of this paper will be treated simply as
a black box that works to solve it. Their algorithm is proven to run in O(3*N^2 + 3*N). (5).
So, the composite running time of the total algorithm of this paper is: O(N log(N))*O(3*N^2 + 3*N)
which comes out be O(3*N^3*log(N) + 3*N^2*log(N)) which is less than O(N^4) and is therefore in P.
Second Attempt at Solution Performed Without Using Graph Isomorphism In the second attempt at solving the
SAT algorithm, it is since discovered that it is not actually needed to invoke the concept of Graph Isomorphism.
The reason for this is because in the process of checking whether two propositions are identical, (the
"Equivalence Algorithm"), it is discovered that there is no need for a total test of equivalence of the two
expressions. The only thing that is needed is to check and see if the two expressions are or are not identically
spelled. The other mathematical case of "equivalence" - which would be for the case where two expressions are
identical but not spelled out the same way - is simply not needed to successfully compute the answer to SAT
and the result of P = NP. I will give the following explanation for this: The scenario breaks
down into eight different mathematical cases. The first case is for the scenario that the two expressions are
SAT but not equivalent to each other, (yielding SAT = T). The second seven cases are for the scenarios where
the two expressions have any other of the possible combinations of SAT and Equivalence not found in
the first case.
Basic Claim of the Improved Algorithm:
Case 1: F = P and Q and (P !EQ !Q), and (P = SAT) and (Q = SAT). Result: SAT = T
Case 2: F = P and Q and (P EQ Q), and (P = SAT) and (Q = SAT). Result: SAT = F
Case 3: F = P and Q and (P EQ Q), and (P = SAT) and (Q != SAT). Result: SAT = F
Case 4: F = P and Q and (P EQ Q), and (P = !SAT) and (Q = SAT). Result: SAT = F
Case 5: F = P and Q and (P EQ Q), and (P = !SAT) and (Q = !SAT). Result: SAT = F
Case 6: F = P and Q and (P !EQ Q), and (P = SAT) and (Q = !SAT). Result: SAT = F
Case 7: F = P and Q and (P !EQ Q), and (P != SAT) and (Q = SAT). Result: SAT = F
Case 8: F = P and Q and (P !EQ Q), and (P != SAT) and (Q != SAT). Result: SAT = F
Expanded Proof of the Basic Claim Given Above:
Case 1: F = P and Q and (P !EQ !Q), and (P = SAT) and (Q = SAT). Result: SAT = T
if (P !EQ !Q) can be solved in P time, then the claim is upheld.
Case 2: F = P and Q and (P EQ !Q), and (P = SAT) and (Q = SAT). Result: SAT = F
if (P EQ !Q) can be solved in P time, then the claim is upheld.
Case 3: F = P and Q and (P EQ !Q), and (P = SAT) and (Q != SAT). Result: SAT = F
if (Q != SAT) can be solved in P time, then the claim is upheld.
Case 4: F = P and Q and (P EQ !Q), and (P = !SAT) and (Q = SAT). Result: SAT = F
if (P != SAT) can be solved in P time, then the claim is upheld.
Case 5: F = P and Q and (P EQ !Q), and (P = !SAT) and (Q = !SAT). Result: SAT = F
if (P != SAT) or (Q != SAT) can be solved in P time, then the claim is upheld.
Case 6: F = P and Q and (P !EQ !Q), and (P = SAT) and (Q = !SAT). Result: SAT = F
if (Q != SAT) can be solved in P time, then the claim is upheld.
Case 7: F = P and Q and (P !EQ !Q), and (P != SAT) and (Q = SAT). Result: SAT = F
if (P != SAT) can be solved in P time, then the claim is upheld.
Case 8: F = P and Q and (P !EQ !Q), and (P != SAT) and (Q != SAT). Result: SAT = F
if (P != SAT) or (Q != SAT) can be solved in P time, then the claim is upheld.
That conclusion has to be sustained if and only that the problem of
whether (P !EQ !Q) can be solved in P time. The proof of that is as follows:
Lemma 1: If P is literally the same as Q, then SAT can be solved in P time, because the
time to check for literal equivalence is in P. (O(n)).
Lemma 2: If P is not literally the same as Q, but it is canonically equivalent to Q,
then SAT can still be solved in P time, because of the following delineation of the
mathematical cases involved:
Case 1: The result is intended to be (SAT = T).
A. P will check as SAT
B. Q will check as SAT
C. (P !EQ !Q) will not check, and the result will confirm as SAT
Case 2: The result is intended to be (SAT = F).
A. P may or may not check as SAT and the result will confirm that the SAT algorithm is
correct.
B. Q may or may not check as SAT and the result will confirm that the SAT algorithm is
correct.
C. (P !EQ !Q) will divide into four cases:
(P = Q) (literally), The result will check.
(P = Q) (not literally, but canonically). The result will check.
(P != Q) (literally). The result will also check.
(P != Q) (not literally, but canonically). The result will check.
The resulting algorithm will tend to run in a running time of approximately O(n log n).
Here is still another algorithm that can be used to demonstrate that the equivalence algorithm
can run in P time. It proceeds by the method that an two expressions being tested for equivalence
can either be of the following nine cases:
1. A is an Not and B is an Not.
2. A is an Not and B is an And.
3. A is an Not and B is an Or.
4. A is an And and B is an Not.
5. A is an And and B is an And.
6. A is an And and B is an Or.
7. A is an Or and B is an Not.
8. A is an Or and B is an And.
9. A is an Or and B is an Or.
The proof then depends on expounding on those cases. The running time is no worse than the worst case,
which is when both A and B are Ands.
The following algorithm explains what to do for that scenario:
1. Let A = C and D, and let B = E and F.
2. Then compare C with E for equivalence recursively. If they are not equivalent, terminate with
Equivalence = False.
3. If they are equivalent, then compare D with F. If they are not equivalent then terminate with
Equivalence = False. If they are equivalent, then terminate with Equivalence = True.
4. Then compare C with F for equivalence recursively. If they are not equivalent, terminate with
Equivalence = False.
5. If they are equivalent, then compare D with E. If they are not equivalent then terminate with
Equivalence = False. If they are equivalent, then terminate with Equiivalence = True.
The proof that that algorithm runs in polynomial time is as follows:
1. The comparison of the two sides, A and B depends on the matching up of the items in the bottom
leaves of the trees that make the expressions. The problem of comparing the two sides of the
trees depends on twisting the various possible matchings of the trees until one successful
matching is found. If two trees are both consisting of And expressions, then the following
table of the Big O computation can be constructed:
1. For two trees of height 1, the running time is O(2). = O(k).
2. For two trees of height 2, the running time is O(4) = O(2k),
because there can be four configurations of the matchings.
3. For two trees of height 3, the running time is O(16) = O(8k),
because the there can be sixteen configurations of the matchings.
4.
5.
6.
7.
Now, at this point, I need to discuss with you the readers what is the formal mathematical proof of the
above algorithm which has been stated here.
There are two propositions to the proof of the algorithm which work together to prove this thesis.
The first proposition is that:
#1 – The above mentioned algorithm solves the problem of SAT, irrespective of whether or not it
terminates in Polynomial Order Time.
The second proposition is that:
#2. - The above mentioned algorithm does in fact terminate in Polynomial Order Time, irrespective of
whether or not it correctly solves the SAT problem.
When those two propositions are formally proven and that placed together, the conclusion is that P=NP.
The proof of the first proposition is as follows:
#1 – The cases for Not’s and Or’s are tautologies. This is because they don’t make any sophisticated
arguments of recursion.
#2 – The case for And’s are more complex and consists of a group of tautologies that work together to
create the larger proposition of the proof on And’s. This proving work requires an extensive enumeration
of a large number of sub-propositions.
• A and Not A is Not Satisfiable.
• If A = Set of Literals and Not A = Set of (total set – A), then again A and Not A is Not Satisfiable.
• If A = B then A and B is Satisfiable.
• If A <> B then (A and B) is sometimes Satisfiable and sometimes Not Satisfiable.
• If A and B has one variable not in common then A <> B.
• If A and B has one variable not in common then either A <> Not B or Not A <> B.
• Case 2 of D is equal to Case B.
The proof for the second proposition that the algorithm runs in P time is as follows:
#1 – The proposition can be stated in a high level language such as Pascal or C# that runs on a Von
Neuman architecture machine with a stack and a heap inside the internals of the software
architecture. The running time is thus no worse than O((log(2) of N)^2) But that running time is no
worse than O(n^2) which is a polynomial.
#2 – The proposition also has the characteristic that it runs on a hypothetical construct which is an AST
in the form of an infinite binary tree. This is exactly the idea of the machine. The processing of the
AST occurs inside the high level C#-like language.
#3 – The proposition has the added characteristic that the memory accesses of the AST occur in k
(constant) Order Time.
#4 – It therefore follows that the running time of the enumeration of the binary tree has an outer algebraic
construct of O(n log n), (the time to traverse an AST), times the Big O of the inner construct, which is
a black box in the theory of “Structured Programming”.
#5 – The internal running time of the black box is no worse than O(n^2) when the memory accesses of the
internal mechanism that operates the black box run in k (constant) order time.
V. PROGRAMMING OF THE ALGORITHM
We created a piece of software called “NPCOMP” whose purpose is to implement the above mentioned
algorithms in the C# Programming Language. Our intent was to not only demonstrate that it solves the
SAT problem in polynomial order time but that it could also be used to further a real world application of
the idea which we chose to be the problem of logic circuit layout for computer architecture. This is one
of many applications which could have been chosen to make a demo example that solves a real world
problem. The SAT algorithm is one small component of this software. Currently, the software is under
development.
V. CONCLUSION AND FUTURE WORK
Our intent is to deliver the software solution to the general public as a desirable application. The payoff
of this work is when SAT is applied to the MaxSAT algorithm as a subroutine. This is how the internal
mechanism of the logic circuit design software works. It is designed to minimize the physical size of the
logic circuitry to save electricity and also run faster when the circuit is smaller. MaxSAT is a special
case of SAT that invokes SAT as a subroutine. MaxSAT may be used to solve for Linear Programming or
Integer Linear Programming by a process that treats the solution with Binary Coded Decimal numbers.
MaxSAT takes the SAT algorithm and puts it to use as a more real world type of optimization problem
suitable for turning NPCOMP into a host of various software packages that ca be implemented for all of
the various cases of the NP-Complete Problems. Here is the general outline of the design of the coding for
MaxSAT. (It is not pseudo-code, but it is written as an English language description).
1. Let there be a function which counts the size of the final solution SAT expression. An example of such
a function is to add up all of the nodes in the binary tree with an additional weight per node based on the
size of that node’s leaves. There are more than one of these functions possible in the general case of the
design of electrical circuits, but this one is the most common and the most needed.
2. State the size as the result of the addition of several Boolean numbers where each of these numbers is
the individual size elements in #1.
3. State the addition of the Boolean numbers a collection of Boolean SAT problems, one for each of the
Boolean digits in the binary number that stands for the total size.
4. Solve the bits as SAT problems in the order of the highest order bit to the lowest order bit. You are
solving for the values of the literals in the original SAT expression and trying to derive the values that
stand for the individual nodes variables in the original SAT expression.
5. To minimize the number of the circuit, try to solve the bit as a 0 first, and then proceed to the next bit,
Taking 1 as the solution only in the worst case. This means that the variables bound in the prior bit
become activated in the next SAT solution bit problem.
6. After resolving which nodes are SAT or not SAT in the original expression, go back and prune out
those nodes which are either 100% SAT, (replace them with T for True), or 100% !SAT, (replace them with F
for False). This yields the final expression for the original SAT expression minimized to the maximum extent
which it can be minimized.
7. If the original expression is either 100% SAT or 100% !SAT, record that fact to minimize the solution
that chosen literal value of T or F.
REFERENCES
1. Knuth, Donald, “The Art of Computer Programming” Volume 1 – Fundamental Algorithms,
Addison Wesley, 1968
2. Gary, Michael R. and Johnson, David S., “Guide to the Theory of NP-Completeness”, W. S.
Freeman and Co., 1979
3. Woeginger, G.J., “P versus NP”, http://www.win.tue.nl/~gwoegi/Pversus-NP.htm, Sept. 26, 2016
4. SATLive.org, “SAT Live!”, http://www.satlive.org/, June 29, 2017
5. Dharwadker, Ashay and Tevet, John-Tagore, “The Graph Isomorphism Algorithm”,
http://www.dharwadker.org/tevet/isomorphism/main.html, 2009
Leave a Reply