Complexity classes are one way to talk about how difficult or easy a problem is. Complexity theory gets very technical but the basics are actually extraordinarily intuitive, and it's possible to understand the P versus NP issue with very little math background.
The kinds of problems we deal with in complexity theory come in pairs: a "search" version and a "verification" version. For example —
- Problem: sorting.
Search version: input a list of numbers X and output the same list in sorted order (call it Y).
Verification version: input a list of numbers X and another list Y, and output "YES" if Y is the sorted version of X and "NO" otherwise.
- Problem: graph coloring.
Search version: input a network of nodes and edges X, and output colors Y for each node such that no adjacent nodes have the same color.
Verification version: input a network X and a set of colors Y and output "YES" if all adjacent nodes have different colors and "NO" otherwise.
- Problem: partition.
Search version: input some numbers X and divide the numbers into two groups that add up to exactly the same value (call the assignment of numbers to their group Y).
Verification version: input some numbers X and the groupings Y and output "YES" if the two groups add up to the same value, or "NO" otherwise.
This is the P versus NP problem:
Are there any problems for which the verification version can be solved efficiently but for which there is no efficient solution to the search version?
If there is a fast solution to the search version of a problem then the problem is said to be Polynomial-time, or P for short. If there is a fast solution to the verification version of a problem then the problem is said to be Nondeterministic Polynomial-time, or NP for short. The question of "P=NP" is then the question of whether these sets are identical.
(The "nondeterministic polynomial-time" terminology is terribly counter-intuitive in my opinion. It was used originally because whenever a Turing machine can efficiently solve the verification version of a problem, a non-deterministic Turing machine can efficiently solve the corresponding search problem. But this is really not at all important to understanding P vs NP.)
In the case of the sorting problem above, there are fast algorithms for both the search and verification versions. But for the other two problems, the verification versions are easy (heck, my grandmother could probably write a computer program to check that two lists of numbers add up to the same value) but the search versions are difficult, and indeed there are no fast solutions known. So all three problems are in NP, but only the first is (known to be) in P.
Some problems can be translated into one another in such a way that a fast solution to one problem would automatically give us a fast solution to the other. There are some problems that every single problem in NP can be translated into, and a fast solution to such a problem would automatically give us a fast solution to every problem in NP. This group of problems are known as NP-Hard. Some problems in NP-Hard are actually not themselves in NP; the group of problems that are in both NP and NP-Hard is called NP-Complete.
You start to see the far-reaching implications of a fast solution to any one problem in NP-Hard: we would automatically get a fast solution to every problem in NP, which would mean that whenever there is a fast solution to the verification version of a problem then there is always a fast solution to the corresponding search version.
Remember how the verification versions of those problems seemed easy but the search versions seemed hard? A fast solution to any NP-Complete problem would mean that as long as you can verify proposed solutions to a problem you would never need to search through a substantial fraction of the search space to find solutions; there would always be a faster way. This seems implausible to most mathematicians (and for deeper reasons that I've listed here) and that is why most mathematicians think that there are no fast solutions to NP-complete problems. But we haven't proved it yet.