#TechWritersChallenge P vs NP

P vs NP is probably the most important theoretical question in computer science, and it's really all about the nature of difficult problems.

You see, some questions in CS are relatively easy to answer —here “easy” or “hard” is used in terms of computational cost, so may as well call them “cheap” and “expensive”—; while other questions, no one really knows, but it seems there is no easy (cheap) way to answer them.

For example, if you have a map with several locations that you need to visit, the question “is there one location B closer than X kilometers to some location A?” is pretty easy to answer. However, a similar question, “can we visit all locations in a tour while traveling less than X kilometers in total?” is one for which we have no solution that is, in general, cheaper than just trying out all possible tours.

The former is a type P question (meaning Polynomial) while the latter is an NP type question (meaning Non-deterministic Polynomial, which is a detail I won't get into).

P =? NP is basically asking whether some NP problems are actually instrinsically harder (meaning exponentially more expensive) than others, or if we just haven't found good enough algorithms yet.

In fact, some NP problems, like our previous example, are so difficult, that if you find a fast (polynomial) algorithm for just one of them, you could solve all other NP problems just as easily. These are called NP-Complete, and their existence is a strong signal that P most likely isn't equal to NP, or so most computer scientists believe.