P=NP Analysis and Theory of Proof

 

 By Dhruv Sharma, Independent Scholar, Arlington VA

 

Summary

This article reframes one of the most important unsolved mathematical and computational problems, the question of P=NP.  The approach presented here posits that this problem is not really a problem and reframes NP problems as ill framed problems which present a class of problems to be solved with all possible parameters instead of specific instances of problems with specific parameters.  By formulating problems this way we can steer clear of NP problems by recognizing them as ill formed or frame problems.

 

 

 

Framing the Problem

It appears that the majority of the field in Computer Science views the problem of P vs. NP view problem solving with a hidden assumption. The assumption is that NP problems and P problems are equivalently framed.  This means that people assume P and NP problem formulations are comparable.  This is a false assumption. NP problems are problems that are poorly framed and result in too expensive approaches to problems in terms of search.  One of the reasons that stochastic search works well is that it fills in numbers and solves tangible possible problems in the poorly defined search space of NP. (Of course nature loves these problems and thus creates NP problems and solves them reasonably well with stochastic search; as show by Dorigo’s AntColonyAlgorithm (Dorigo).

 

A simple example of P vs. NP from the Clay foundation is as follows:

Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971. (Millenial Problem Website: http://www.claymath.org/millennium/P_vs_NP/ )

 

 

A Different Approach

If a problem appears to be NP then it has not been framed properly and that the problem has been made too general.  Why should it be necessary to solve every possible instance of problems instead of a specific problem with specific constraints? I see NP as trying to solve all possible sets of particular problems rather than solving defined problems.  This is why NP problems appear hard because there is nothing harder to solve than a poorly framed problem.

 

If one were attempting to prove P=NP then one would not begin by solving NP problems in P time as this would be a waste of time.  Ironically this is opposite of what the Millenial Problem statement mentions as an obvious approach to the problem (Cook).  Instead the trick is to take a P problem and frame it in a general manner in which it becomes NP in its solving.  This in effect would prove P=NP.

 

An Approach/Attempt to Proving P=NP

An example of proving P=NP would be as follows. 

Facts:  We know the 2 SAT problem is satisfiable in P. 

We also know that 3 SAT is NP complete. (Moshkovits; Russell & Norvig , 2003))

Inference:

If 2 SAT can easily be converted to 3 SAT then 3 SAT would become NP and thus NP=P.

 

2 SAT problems are of the form (A or B) and ( C or D) etc. where A,B,C etc are logical propositions.

 

3 SAT appears as follows:  (A or B or C) and (D or G or A) etc…. where A,B,C etc are logical propositions.

 

Substitution Algorithm

Using substitution I suggest the following algorithm of converting 2 SAT to 3 SAT:

1)      For each 3 literal clause take an arbitrary disjunction in a clause and replace them with a fictional literal.  For example:  B would be replaced by Zi or Xi.

 

This in algorithm should in effect transform a 2 SAT problem into a 3 SAT problem which can them be solved in P.  Ironically the first time I approached this I did the reverse and reformulated 3 SAT as 2 SAT similar to Smullyan’s friend who solves math problems by incorrectly doing the opposite of what he sets out to do(Smullyan, 1980).

 

Further Work

There may be a flaw in this approach if so please correct it you can.  I think the overall approach is correct but my algorithm could be flawed.  I intuitively feel this approach is correct although I may not be able to prove it within an axiomatic system (as indicated by Godel’s Incompleteness Proof (Hofstadter, 1979).  The key point of this line of reasoning is that only problem with NP problems are that they are poorly framed and cannot be solved as they are not specific instances of problems to be solved but rather all classes of problems.  Mother nature does not solve or frame NP problems, humans do, and humans would be wise to specify specific problems to solve. Nature simply used stochastic, random answer based solutions to deal with NP like phenomenon where evolutionary good enough solutions proffer depending on the fitness landscape or current states of nature.

 

 

References

 

Cook, S. The P versus NP Problem. Retrieved from http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf

 

Dorigo, M. (2004) Ant Colony Optimization. MIT Press.;

Also see retrieved from http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html

 

Hofstadter, D.R., (1979) Gödel, Escher, Bach: an Eternal Golden Braid, New

York, Vintage Books

 

Moshkovits, D Where Can we Draw the Line: The Hardness of Satisfiability Problems Retrieved from  www.cs.tau.ac.il/~safra/Complexity/2SAT.ppt

 

Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall

 

Smullyan, Raymond. (1980) This Book Needs No Title: A Budget of Living Paradoxes. New York, NY: Prentice Hall