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.
*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!
