Your scrolling text goes here
Your scrolling text goes here
top of page

The Greatest Puzzle in all of Computer Science

Oct 3, 20247 min read

Computers have become a fundamental part of the world and inherently our lives and they have brought a plethora of benefits that aid in daily life. They are able to solve many problems that would take us humans millennia to do. This raises the question: are computers able to solve even the most complex problems, or are there limits to their surrounding abilities?





The P vs NP problem is one of the greatest unsolved mysteries in computer science and continues to stump many famed mathematicians and computer scientists for over 50 years. This problem, if solved, has the potential to bring vast changes and challenges to our world that can fundamentally alter the way we live. The Clay Mathematics Institute is offering a $1 million prize for its solution. Are you up to the challenge?


P VS NP

The basis of this problem is that there exist two types of problems in computer science, P problems and NP problems. P problems are problems that have easily-developed algorithms; an algorithm is essentially a set of instructions on how to solve said problem.  They are also able to be done and solved in polynomial time. NP problems on the other hand do not have easily made-up algorithms nor can be solved quickly but can be verified if a solution is correct, which we will touch on later.


The key difference in these problems is that P problems can be solved in polynomial time, while NP problems cannot. Polynomial time is something that may be familiar to some and essentially means that the time it takes to solve a problem is bounded by a polynomial, as the input increases in complexity.


Consider this problem where you want to determine the shortest path somewhere. This problem has a simple algorithm that can be applied to any sized input. When we program this, the time complexity may come out to n², which is a degree 2 polynomial. You can imagine a graph of this, which would be a parabola, and as the input increases in size so does the output, but it increases by a common factor which means it has polynomial time and can be easily solved by computers.


Now consider this: what if we had a problem that had a time complexity of 2^p? now we have an exponential time, which is not polynomial and, unlike polynomial, exponentiation increases at a far greater rate, making it hard for computers to solve problems for complex or large inputs. 




The Problem

Now that we have established what P and NP problems are, let us dive deeper into these problems and see what we notice.


As computers progressed and were able to do a multitude of other tasks, computer scientists quickly realized not all problems are solvable, even by computers. They found that some problems were relatively trivial for computers to do, but others stumped even the fastest of computers. Simply put, for some problems it is extremely difficult to come up with an algorithm, and without an algorithm, there is no way to program a computer to solve a problem. To put this into perspective, these difficult problems would have to have algorithms that have more steps than there are subatomic particles in the entire observable universe, it is simply infeasible.


As established, P problems are the problems where algorithms can be made up easily and thus these are the problems that are easy for computers to solve. All of our daily tasks and interactions with computers are done through P tasks or P problems, and this can include anything from mathematical operations to sorting names alphabetically. P problems grow polynomially, and as a result, are able to be solved efficiently by computers. On the other hand, NP problems are problems that take non-polynomial time to solve and can include something such as exponential time. A key feature of NP problems is that they are easy to verify, which means that given a solution it can easily be verified if it is correct or not.


Consider if we had a Sudoku puzzle with a size of 10^100 x 10^100. How can we create an algorithm to solve it that also works for any other sized input? It seems impossible. However, if given the solution we can easily verify it because we can easily calculate the rows and columns. Now, this also means that P problems are actually a subset of NP problems as they too can be verified quickly. However, there exists a sub-class of NP problems that are incredibly difficult to solve, and nearly impossible, such as the Sudokupuzzle. In a sudoku, it is hard to solve at first but once you do you can easily verify it, as we increase the input or the size it becomes exponentially harder which is why it is extremely difficult for computers. The exponential growth of complexity makes it nearly impossible to solve unless for clever algorithms but to develop these is not easy. Over time, computer scientists were able to develop clever algorithms that are not done by brute force of trying all possible computations, but by taking advantage of certain manipulations to solve these difficult NP problems. When NP problems are able to be solved through an algorithm they can now be classified as P problems.


Now, the question that has eluded computer scientists to this day is if all NP problems are really just P problems. In short, can we create clever algorithms for all NP problems so that they become P problems? Does P = NP?



Solutions 

Since this problem's inception over 50 years ago, many advancements have been made but no formal solution has been found to prove if P does in fact equal NP. However, there have been many notable advancements that have been made that allow us to grasp a better understanding of P and NP problems.


For one, in the 1970s two computer scientists Stephan Cook and Leonid Levin discovered the concept of NP-completeness which vastly changed the magnitude of this problem. NP-completeness means that all NP problems that are notoriously difficult, and remain unsolved are very similar at the center, and a single algorithm can be mapped to all of them. This means that by solving one complex NP problem or proving one to be equal to P, then you can prove very easily all the rest are equal to P as well and will have solved the problem.


However, as of yet, no one has yet solved and come up with the algorithm for any of these complex NP problems. As a result, it remains unsolved to this day, but it is possible that in the future significant breakthroughs can lead to a solution and with it, will bring about a paradigm shift in our world. 


Consequences 

This problem is extremely difficult to prove because to do so means we have to solve and come up with an algorithm for all NP problems, so as of now we cannot say P = NP. As of now, the vast majority of computer scientists believe that in fact, P does not equal NP unless a formal proof is made, which requires NP problems to be solved. 


The consequences of this proof can be far-ranging and would come with a numerous amounts of benefits but also many detriments. It would allow us to virtually solve any problem with computers allowing us deep insights into our world, in fields like space exploration and medicine. It can empower businesses to solve problems and use AI to predict trends and the future with prediction rates of nearly 100%. However, if P = NP there exists a great downfall, as that means any problem is solvable, which also means any computer encryption is also breakable as they are just complex problems. If P truly equals NP, all current-day encryption methods become futile, which puts everyone at risk. Your bank accounts, your medical records, even your identity, can all become compromised and put lives at risk, and compromise your privacy.


Although opinions are not all that relevant when we speak on theoretical sciences, I feel with a problem as abstract as this it is important to have opinions, and for me, I am a firm believer that P does not equal NP. In a poll conducted by the University of Maryland over 61% of people believed the same whilst 9% held out that P does in fact equal NP, what do you think?


Conclusion

In the world of theoretical computer science, the P vs NP problem remains one of the field's greatest mysteries, and it remains unsure if we will ever uncover the proof behind it but maybe it is for the better. As Scott Aaronson said, “If P=NP, then the world would be a profoundly different place than we usually assume it to be.”  Despite our collective pursuit  and determination for knowledge, maybe it is best to leave some things unsolved, as there is no telling what the consequences can be for the digital age if P does really equal NP, as on one hand, it may bring miracles in scientific discovery. But, on the other hand, it can become a detriment to our digital world, with hackers and intruders having newfound capabilities to compromise our privacy. In the end, this problem will likely continue to remain unsolved, but there exists a great plausibility that in the future, a significant breakthrough can lead to what is needed to prove if P = NP.


 

Written by Akishai Sabaratnasarma


References


Comentários

Avaliado com 0 de 5 estrelas.
Ainda sem avaliações
Adicione uma avaliação
bottom of page