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!           

  

Dreading the El Nino spiked heat wave

 

The world has already entered unchartered zone of climate that is having detrimental effect on biodiversity this in turn is putting pressure on resilience of ecosystem eventually food security and survival of life. Democratic institutions and social cohesive values are facing severe pressure. Eventually vulnerable population will have to pay a heavy price while growthism extremist fatten themselves on carcass of arguments. In disparities driven poor societies desperate people will die in millions while millions more pushed into worst of living condition, and as expected these will be easily managed and manipulated into insignificant matter in the mainstream narration. Witness how ‘developed’ country with high standard of living and awareness like Britain is being dealt by utter scoundrels as politicians. It is not an accident, these are systemic, and these very deviant value systems severely damaged fledgling democracies of post-colonial exploited nations across the world, which in turn infected international institutions. If this is how critical institutions are framed then how will the world deal with existential threats? Feudal value systems were actively nurtured into democratic institutions reducing it to a farce, easily susceptible to nepotism, corruption and manipulation. From Africa and Asia, the extent to which sun never set, democratic institutions are being used for control and exploitation. Economists work out the detail while market media chisel the liberal sounding semantics for the audience while common people see the world collapse around them. The wanton colonial hypocrisy of rule of law by racist colonial monarchist christian civilizers became a compelling ideal for local charlatans. Hence democratic institutions and values of freedom and liberty were curtailed in the initiations itself. Egalitarian values are sidelined while humanitarian concerns dealt in posturing. Even amazing possibilities of technology is reduced to worst of dealing. Humans are actively sought to be dehumanized into herds for exploitation. Herds happily dull in Huxleyian entertainment while being told by guardian posers to fear Orwellian incursions. Distraction and manipulation, and containment, is how history repeats for herds. Charlatans worked critical debates as juvenile skirmishes of adolescents to keep the entertainment going. Attention economy is how homo sapiens have collectively worked to value itself.

There are enough signs that climate systems are collapsing faster than anticipated. Earth is heating at an unprecedented rate. As the Indian subcontinent moves towards summer this year El Nino is expected to make it worst. We are facing serious dangers of heat waves and forest fires. Though one hopes authorities are prepared but I really don’t see much action. Market media and herd controllers are excited about elections. Election Commission of India seems to be least concerned about plight of people, and expect them to come out to vote during heat wave conditions. It seems officials at EC are incapacitated to anticipate (like cricket wastrels surprised at rain in the venue during monsoon!). Understandable when all your life you were manipulating, conniving, genuflecting, for power and position. Mediocre society lacking intellectual class or tradition of probity or critical thinking also values these petty bureaucrats as reservoir of wisdom carefully emulating the template of colonial masters. COP28 cosmetic approach includes ‘cool pledge’, a ‘commitment’ to reduce climate impact of cooling sector and also universal access to life saving cooling. Meanwhile Heat Action Plan are only guidelines while NDMA initiated ‘Cool Roof’ seems to be the only action taken with some seriousness, ofcourse it is life saver in congested areas of cities, and will reduce heat island effect. Kerala has taken initiative to create cooling centers, but converting makeshift pandals into permanent structures in congested areas will need air-conditioning. AC/refrigeration already contributes to about 7% of GHGs, and then there is issue of continuous power generation during peak demand. What is needed is sustainable strategies. Before electric fans were introduced people in this region had many traditional methods to keep themselves cool that includes the way buildings were designed. These could be explored, like for instance, well ventilated high raised ceilings tend to be cooling. I read that some churches have shown enthusiasm to be converted into cooling centers, the way churches are designed provides natural cooling. Meanwhile citizens must make themselves aware of increasing temperature threshold of the region they are located in. They must take action to create off grid source of power as also natural ventilation and building design with vast resource of traditional knowledge and latest technology. Devious power structure will seek attention and keep you distracted as they amass and satisfy their ever burgeoning greed. When push comes to shove -as it happened during pandemic, you will be abandoned in the streets to die. Beware people retrieve your humanity from the herd. Technology is offering transparency and with collective action much can be worked out.

*In the low-lying regions where water logging has become frequent people have started to construct adaptive buildings. This I saw on my walk.

                  

 

Understanding

When you realize your being

has started the preparation to seep into timeless.

The carbons, the hydrogens, the oxygens…

loosen their grip on miracle.

The joyous bouquet of warblers decides to disperse

into their lonely way.

Withering senses too weak to show its final gratitude

for the marvel of chance.

You close your eyes in reverence

for all that was shared

as the setting sun dims the scene.