Thursday, February 29, 2024

P versus NP complexity problem

 

P vs NP is a profound problem at the intersection of theoretical computer science, computing technology and mathematical logic. It is a problem that is vexing computer scientists, researchers and mathematicians everywhere for many decades now, and is considered the most important problem of times we live in. Is P=NP? is indeed a profound question that has enormous significance to humanity. If P=NP is proved then it will give enormous power over knowledge. World will not be the same again. There will be no gap between solving a problem and recognizing the solution. If P equals NP, then you could solve anything as easily as you could verify it. Fundamentally what it means is that if we can quickly check that a solution to a problem is correct then we can also solve the problem quickly. Hence anyone who could drive a vehicle could build one, and anyone who listen to a symphony could create it like a Mozart. It is crazy but that’s what it is.

Since it holds course over fate of humanity let us try to understand what exactly is this problem. It isn’t that difficult to understand. P stands for Polynomial time wherein number of computational steps grows as a power of number of variables rather than exponentially. What it really means is that we can predict the maximum amount of time it will take to solve the problem. P problem is therefore is easy and tractable, feasible to solve. Time to compute the solution is not out of reach. Solution is also easy to verify -that is, to check whether the answer is correct. So, a computer can solve a P problem in reasonable amount of time and also verify it instantly. Algorithm exists for its solution, and the number of steps is bounded by a polynomial function of n. Polynomial is ‘raised to the power’ or exponential which is also a number -hence bounded to time, this number is number of inputs to the problem, that is, number of steps algorithm needs to take is proportional to input size. NP stands for Non deterministic Polynomial time. Problems that can be verified in polynomial time but may take exponential number of steps to solve. What it means in simple terms is problems that take long time to calculate but short time to verify. Solution can be guessed or verified in polynomial time in a non deterministic way, that is, no particular rule is followed to make the guess. There are no formulae to predict how long it will take to solve a NP problem. The only way to solve the problem is to keep trying the answers until we find one that works. Time required to solve the problem using any currently known algorithm increases tremendously as the size of the problem increases hence it may take millions of years to find the solution using the available computational power. Therefore, NP problems are those whose answers are relatively easy to verify but there is no easy way to compute a solution. NP problems take time to solve but are easy to check once solved. The time taken to find solution grows exponentially as the size grows. Simple examples of these are puzzles. To solve the puzzle, you may have to use all your creativity and experience while verifying each step before finding the solution, and once solution is found verification can be done easily. Sudoku is an NP problem that takes time and effort to solve but once it is solved it is easy to check whether it is correct, and the time required to find solution increases exponentially as the game grid increases. Optimization problems, scheduling, designing or routing (travelling salesman problem) that searches for optimal solution are simple examples of NP problems that are easy to check or verify but difficult to solve. So, P and NP are complexity classes, it also includes NP Complete (NP-C), these classes are based on how difficult they are to solve.   

Some NP problems are found to be P problems. Like for instance Linear Programming problem was once classified as NP -as the number of steps increases exponentially with size of input, but polynomial time algorithm was discovered for linear programing showing it as P problem. Another example is that of testing whether a number is prime, this was NP class problem but in 2002 clever algorithm showed it to be P class problem. Hardest problem in NP, referred to as NP-C, are never shown in P. These problems are too hard to be solved with current methods. Interestingly if one of the NP-C can be shown to be in P then that means all NP-C are in P. So, P=NP essentially means; Can every problem in NP be solved in polynomial time? Can exponential time problems be solved in polynomial time? Are questions that are verified in polynomial time also solved in polynomial time? What it means is that every problem that can be verified quickly can also be solved quickly. This has profound implication as we can solve anything as easily as we can verify it. Finding solution becomes as easy as verifying that the solution is correct. This also brings in bigger question of how we decipher problems. Do we try to know and then figure it or do we work at the solution before finding it? And if P!=NP (N not equal to NP) then it means that some problems are beyond the ability of computers to solve even with tremendous computing power. Highly abstract nature of problem may need something more nuanced than brute computational power.  

PvsNP problem is essentially asking whether efficient solutions exist for complex problems or that some problems are inherently difficult to solve quickly. It also raises deeper questions on nature of knowledge, process of acquiring it and limitations of understanding. There is a view that PvsNP is a problem beyond mathematics, that the basic axioms that is accepted are not enough. Checking astronomical number of possibilities one by one will take millions of years even with brute computation force algorithm. We do not have any useful information, priori, to discriminate some solutions hence reduce the set and therefore are forced to iteratively work all the solutions. If deterministic digital computers have limitations, then what about quantum computers? Famously Shor has shown that some quantum computer algorithm is capable to solve NP problem in polynomial time. It is proved that large prime number based digital encryption could easily be decrypted by Shor’s algorithm hence the rush for post quantum cryptography (indeed public key codes that exploit asymmetry in encoding and decoding i.e. encoding is quick and decoding slow, are equally susceptible to P=NP solution). Shor’s algorithm was able to use quantum to exploit hidden structure existing in factoring. But we still don’t know whether such structures exist in NP-C problem. Furthermore, quantum computer taps on properties of matter that exist simultaneously in different states, and use these multiple states in parallel to explore different possibilities, the information is stored in spin of electron but the observer effect changes the result and also limit access. The difficulty to prove P=NP means that it is not possible to solve an NP-C problem. Just as Godel’s incompleteness theorem shows existence of unprovable theorems there may be intrinsically random problems that lacks logical scheme to solve quickly. Or is it that level of abstraction and complexity required to solve NP-C problems is difficult for human mind to comprehend or language to express? Our language to access reality seems to have shortcomings. Is the language game creating paradoxes that weaves away from nature, hence the difficulty in accessing? There is a reason why Turing was frustrated after listening to Wittgenstein lectures!  

So, the question essentially remains the same: How can we access the solution in polynomial time without going through exponential time frame search? Can we still zoom into solution where brute computation and quantum seems to fail? Does N!=NP points to limitation of human reasoning? Is this limitation of nature, as in, ‘laws of nature’? Does recent innovation in AI holds some value? It is clear that AI is limited by same constraints as humans, it cannot really solve problem that requires more resources than are available in physical universe. Importantly, complexity of PvsNP needs deep mathematical understanding and creative problem solving abilities which maybe beyond the capabilities of existing AI algorithms. They really cannot generate novel solutions as they imitate or reproduce existing proofs. Despite these negative prognosis and general cynicism AI do hold possibilities. There are enough examples of emergent abilities and capacity to detect patterns that is simply astounding. So, it is possible that AI can leverage massive amount of data, deep learning innovations and powerful computation to explore and extrapolate large and complex search spaces to come out with something entirely unexpected, or even efficient algorithm for NP-C problem. AI based evolutionary algorithm that function in Darwinian like natural selection are being adapted to learn from existing proofs and algorithms to generate new ones and solve complex problems. AI is already challenging exclusive human claim on thinking and access to rationality. And for some it has already blurred P=NP through DeepMind’s Alphafold by solving ‘protein folding problem’. Protein folding is an NP-C problem. For some AI didn’t really solve ‘protein problem’, since it didn’t work out any polynomial time algorithm. It is a optimal heuristic solution, and that protein probably did not fold to absolute minimum energy but to local minimum. Global minimum, or absolute minimum, potential energy is NP-C, and since polynomial time algorithm cannot solve, we have to assume that nature also cannot (otherwise it will take exponential time, and so nature is essentially inefficient!) hence it folds to local minimum and not absolute minimum. There is something serious amiss in this argument. Way back in 2004 there was an attempt to prove P=NP using soap bubble as a mechanism for analog computer. Soap bubble film naturally align to minimum energy configuration.

Universe is an uncertain entity. We live and evolve in the edge of chaos and are in constant loop with it. The problem could be the uncertainty and inability of limiting semantics and the complexities arising from fixed frame trying to contain dynamic chaos. I will put my money not on P=NP nor P!=NP  but on P~NP. The relation between polynomial time and exponential time is blurred by iterative inputs. Reality represents a frame that is flexible and dynamic, it can only be heuristic optimization. The pattern that is realized in verification as solution is momentary. To attribute this as optimal fixed is a mistake. Nature is alert in its loop with surrounding, and is rarely inefficient. If nature is deemed as inefficient since it is incapable to factor exponential into polynomial then it has to be about incapacity of semantics. If a brainless slime mold can produce dynamic optimal path within few hours, then we need to reevaluate our insight. If tiny insects can orchestrate ‘swarm intelligence’ to optimize resources without any supervision, then we need reevaluate how we view the world. Swarm intelligence is based on simple rules (P=NP) but it is flexible to dynamic changes, creative resourcing and heuristically optimized based on accumulated wisdom of evolution (N!=NP). It is complexity underlying simplicity of universe. The meaning and elegance in managing chaos. It zooms in on to solution working on complexity and abstraction of evolutionary intuition. Evolutionary algorithm is limited by narrow understanding of how nature evolved or what Darwin proposed. Much of nature has evolved through mutualism, symbiosis and heuristic partnering, and wisdom to minimize confrontation and optimize resources. What is needed is algorithm from nature to tap on millions of years embedded wisdom, to seek pattern. This then is the polynomial time algorithm working exponential in polynomial scale. If you listen to music you can attempt to create factoring your surroundings. With creative skills, experience and intuition you can be a good composer or with creative leap a great composer but you cannot be a Mozart. Every path is a unique solution to the time and space context of each.         

*while going through Chinese researchers using GPT for PvsNP I came across interesting prompt engineering that used Socratic questioning and reasoning to generate innovative responses. The problem with GPT is that if your prompt is not creative or cleverly engaging GPT tend to retrieve or regurgitate pre-existing answer or lapse into mainstream template. I found Socratic questioning simple and profound. Similarly, the way GPT learns language also intrigues me (by iterative approximation -essentially Wittgenstein, and not ideal meaning -Plato) it is also the way I learn language. So, I am not surprised GPT makes stupid mistakes!