P=NP Explained: A Layman's Guide

[DR13]

Yesterday, my computer science teacher (intro course) mentioned this mythical P=NP problem. He tried to explain it to the class but it went over everyone's head. Could someone please explain it to me in laymen's terms?
Thanks

 

[D H]

Different problems have different computational complexity. Testing whether a list is sorted is an O(n) problem. Walk through the list, comparing the value at the current node to the value at the previous node. If the list has N elements one must perform N-1 comparisons to determine of the list is sorted. Sorting a list is O(n log n). Multiplying two square matrices is O(n²), but finding the inverse of a matrix is O(n³). In a sense, all of these problems are computationally simple. The time needed to solve the problem is polynomial in the size of the problem.

Some problems appear to be very hard to solve, much harder to solve than the polynomial-time problems described above. The traveling salesman problem is the prototypical example of these hard-to-solve problems. The number of possible routes grows factorially as the number of cities increases. A brute-force approach is nigh impossible for anything but a handful of cities. As far as we know there does not exist a polynomial-time algorithm to solve the traveling salesman problem. The hamiltonian cycle problem is somewhat simpler problem than the traveling salesman problem. The hamiltonian cycle problem just requires coming up with a valid route, but not necessarily the shortest route. However, the hamiltonian cycle problem is, as far as we know, an O(n!) problem.

Finding a solution to a given problem is often "harder" than testing whether a proposed solution is indeed a solution. Sorting a list is O(n log n) but testing whether a list is sorted is O(n). Inverting a matrix is O(n³) but testing whether a candidate solution is the inverse is O(n²). As far as we know, finding a hamiltonian cycle is O(n!) but testing whether a candidate route is valid is just O(n).

Note that verifying whether candidate solution to the hamiltonian cycle problem is a valid solution is a polynomial-time problem. The class of problems in which verifying whether a candidate solution requires polynomial time complexity is the NP class of problems. Some of these problems are known to be "easy" to solve. These are the P class of problems. P is definitely a subset of NP, but whether it is a proper subset is the P=NP problem.

The hamiltonian cycle problem is in a special subset of NP called NP-complete. If a polynomial time algorithm can be found to solve anyone of these NP-complete problems then a polynomial time algorithm exists for all NP problems. Finding such an algorithm would prove that P=NP. That nobody has found such an algorithm does not prove that P≠NP. It only shows that we haven't found the magical algorithm yet.

Or, just maybe that magical algorithm doesn't exist. That is what most computer scientists think is the case. These hard-to-solve problems are hard to solve, period.