If I remember correctly (which I probably don't), it's to do with the time it takes a computer to solve a problem, and the time it takes the same computer to work out if there's a solution at all. And P=NP is when those two times are the same.
I think.
Maybe.
Computers confuse me.
Not quite.
P and NP are classes of decision problems (technically, formal languages but we can forget that for now), and a decision problem is a problem with a yes/no answer, i.e "Given a number
n, is
n prime?".
"P" is the class of decision problems that can be solved efficiently (specifically, in a number of steps that is a polynomial function of the size of the input). A good example of a problem in P would be "Given a number
n, is
n a perfect square?"
"NP" is the class of decision problems that can verified efficiently: If a particular instance of the problem has a yes answer ("Is 25 a perfect square"), there exists some form of short "proof" or example that the answer is yes ("5x5=25"), and that short "proof" can be checked efficiently (with this example, "5" is the "proof" and the method for checking is by squaring 5 and checking that we get 25)
It's pretty easy to see that everything in P is also in NP, the question is whether everything in NP is also in P. Most people (who know enough to have an opinion) think the answer is no. An example of a problem in NP that is (probably) not in P is the traveling salesman problem: Given a list of
n cities and distances between them, and some maximum distance
k (in some unit), is there a way to visit each city exactly once and travel less than
k units? The obvious way of solving it is to check every possible path, but the number of paths is exponential (2^n), which is not very efficient for large
n. Nobody knows a (significantly) faster way of answering the question.