###### Search By Tags

###### Featured Content:

###### Search by Date

December 2, 2018

January 31, 2018

November 22, 2017

October 9, 2017

*P vs. NP*

*P vs. NP*

October 16, 2015

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the original city? This is the travelling salesman problem, and questions like these are the specialty of computer science.

Computer science is the study of computers and their uses. As personalized computers and mobile phones become popular, cloud services and databases collect more and more of our information, making internet security a major issue. Computer science has therefore become one of the most significant areas of science, utilized by schools, corporations, and national governments. By understanding how to access, process, represent, and store data efficiently, the multitudes of information presented to us in our daily lives can be parsed more productively.

The given problem, the travelling salesman, is a NP-complete problem. A NP problem is quickly verifiable, and “complete” means also costly in time to solve. One of the major unsolved mysteries in the computer science world is the P vs NP problem. In basic terms, it asks whether quickly verified problems can also be quickly solved. P problems (quickly solvable) are the set of problems from all problems that can be solved in “polynomial time”, which is the amount of time it takes to solve a problem that is proportional to the polynomial function describing the complexity of the algorithm. An example would be checking for spelling errors and listing them.

NP problems, on the other hand, are the set of problems that can be verified in polynomial time. Many NP problems, however, are called NP-complete and seem to be only solved in exponential time. Take 2N for example. An exponential function like that starts off growing slowly but then skyrockets. As the amount of work increases, the time it takes to execute the function grows significantly. Since NP-complete problems can only be solved in exponential time, this means that NP problems overall are much harder to solve with computers. Another example of a NP-complete problem would be a jigsaw puzzle. Once completed, it can easily be verified to the answer. However, solving the problem requires brute-force, which takes exponentially increasing time.

Therefore, the P vs NP problem asks whether a problem that can be verified in polynomial time can also be solved in polynomial time. This conundrum questions whether P = NP could be true, and whether the two sets, quickly solvable and quickly verifiable, could be the same set. If P is indeed equal to NP, that means for every NP problem, including NP-complete, there is a shortcut that can help computers find a perfect solution, making the problem a P problem. Granted, even if a proof for P = NP was found, it would be difficult to utilize the finding. However, if it is proven, computing time could potentially be shortened drastically, allowing advanced simulations, stronger brute-force, and powerful computers. This might also enable the utter destruction and unpreventable exploitation of our current security systems. Of course, the travelling salesman problem would also be reduced to polynomial time, saving the salesman a few dollars of ticket fee.

Image Source: https://eagereyes.org/media/attachments/ZIPTPCMap-color-names.png

About the Author: Samuel Fu

Samuel is a high school junior from California, USA.

Tags: