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.

 

[quicknote]

for your question! The P=NP problem is a very complex and important question in computer science. To explain it in simple terms, it is essentially asking whether there are certain problems that can be solved quickly (in polynomial time) by a computer, but are difficult (or impossible) for a computer to solve in a reasonable amount of time.

To understand this, let's think about a simple problem like finding the shortest route between two cities. If we have a map and we want to find the shortest route, it might take us a while to figure it out. But a computer can solve this problem very quickly using algorithms and calculations. This type of problem is known as a "P" problem, which stands for "polynomial time."

Now, imagine a more complex problem like finding the factors of a very large number. This is a problem that would take a computer a very long time to solve, even with advanced algorithms. This type of problem is known as an "NP" problem, which stands for "non-deterministic polynomial time."

The P=NP problem asks whether these two types of problems are actually the same - can all NP problems be solved in polynomial time? This is a difficult question that has not yet been answered, and it has important implications for the field of computer science.

I hope this helps to clarify the concept of P=NP for you. It's a very interesting and ongoing debate in the world of computer science, and I encourage you to continue exploring and learning about it.