[computer-science] What's "P=NP?", and why is it such a famous question?

To give the simplest answer I can think of:

Suppose we have a problem that takes a certain number of inputs, and has various potential solutions, which may or may not solve the problem for given inputs. A logic puzzle in a puzzle magazine would be a good example: the inputs are the conditions ("George doesn't live in the blue or green house"), and the potential solution is a list of statements ("George lives in the yellow house, grows peas, and owns the dog"). A famous example is the Traveling Salesman problem: given a list of cities, and the times to get from any city to any other, and a time limit, a potential solution would be a list of cities in the order the salesman visits them, and it would work if the sum of the travel times was less than the time limit.

Such a problem is in NP if we can efficiently check a potential solution to see if it works. For example, given a list of cities for the salesman to visit in order, we can add up the times for each trip between cities, and easily see if it's under the time limit. A problem is in P if we can efficiently find a solution if one exists.

(Efficiently, here, has a precise mathematical meaning. Practically, it means that large problems aren't unreasonably difficult to solve. When searching for a possible solution, an inefficient way would be to list all possible potential solutions, or something close to that, while an efficient way would require searching a much more limited set.)

Therefore, the P=NP problem can be expressed this way: If you can verify a solution for a problem of the sort described above efficiently, can you find a solution (or prove there is none) efficiently? The obvious answer is "Why should you be able to?", and that's pretty much where the matter stands today. Nobody has been able to prove it one way or another, and that bothers a lot of mathematicians and computer scientists. That's why anybody who can prove the solution is up for a million dollars from the Claypool Foundation.

We generally assume that P does not equal NP, that there is no general way to find solutions. If it turned out that P=NP, a lot of things would change. For example, cryptography would become impossible, and with it any sort of privacy or verifiability on the Internet. After all, we can efficiently take the encrypted text and the key and produce the original text, so if P=NP we could efficiently find the key without knowing it beforehand. Password cracking would become trivial. On the other hand, there's whole classes of planning problems and resource allocation problems that we could solve effectively.

You may have heard the description NP-complete. An NP-complete problem is one that is NP (of course), and has this interesting property: if it is in P, every NP problem is, and so P=NP. If you could find a way to efficiently solve the Traveling Salesman problem, or logic puzzles from puzzle magazines, you could efficiently solve anything in NP. An NP-complete problem is, in a way, the hardest sort of NP problem.

So, if you can find an efficient general solution technique for any NP-complete problem, or prove that no such exists, fame and fortune are yours.

Examples related to computer-science

HTML5 Canvas background image What exactly does big ? notation represent? Fixed point vs Floating point number What are the differences between a program and an application? What do we mean by Byte array? How to determine the longest increasing subsequence using dynamic programming? What is "entropy and information gain"? What are the differences between NP, NP-Complete and NP-Hard? What is the difference between statically typed and dynamically typed languages? What is “2's Complement”?

Examples related to theory

while-else-loop Using IS NULL or IS NOT NULL on join conditions - Theory question Why are C++ inline functions in the header? Difference Between Cohesion and Coupling What is a database transaction? What good are SQL Server schemas? How to program a fractal? What is an NP-complete in computer science? Way to go from recursion to iteration What's "P=NP?", and why is it such a famous question?

Examples related to complexity-theory

Differences between time complexity and space complexity? Determining complexity for recursive functions (Big O notation) How to find time complexity of an algorithm How can building a heap be O(n) time complexity? HashMap get/put complexity Big-oh vs big-theta Is log(n!) = T(n·log(n))? Time complexity of accessing a Python dict What are the differences between NP, NP-Complete and NP-Hard? What's the fastest algorithm for sorting a linked list?

Examples related to np-complete

What are the differences between NP, NP-Complete and NP-Hard? What is an NP-complete in computer science? What's "P=NP?", and why is it such a famous question?

Examples related to p-np

What's "P=NP?", and why is it such a famous question?