The One Million Dollar Question

Does P = NP ?

P = NP ?

This is one of the most famous problems in computer science. A correct solution to the question/problem does P=NP, will get you $1 million USD. This problem asks whether or not for all problems that can be verified in polynomial time, can they also be solved in polynomial time ? That is to say can every solved problem whose answer can be checked quickly by a computer also be quickly solved by a computer? -(Wikipedia) This problem is apart of the Millennium prize problems, and was conceived in 1971.

Fig 1: A picture showing ‘P-problems’ are easily solved and easy to verify, while ‘NP-problems’ are easy to verify but have not been proven to be easily solved.

P problems are fast for computers to solve, and so are considered “easy” or problems that can be solved in polynomial time. These are problems like multiplication or alphabetizing a list of names. NP problems are fast (and so “easy”) for a computer to check, meaning they can be checked in polynomial time, but are not necessarily easy to solve. These problems include job scheduling, vehicle routing (TSP), circuit design, Sudoku, and database problems (feedback vertex set), and the Hamiltonian Path Problem which basically says “ given N cities to visit, how can a person visit every city without visiting a city twice. Finding prime numbers was once…