NP stands for "non-deterministic polynomial time". Problems in NP
can be "solved" by guessing their solutions and then checking,
in polynomial time, that the solutions work. For instance, the
Traveling Salesman problem is in NP because once we guess a tour,
it's easy to check whether it is in fact a tour, and whether it's
shorter than the desired length.
P stands for "(deterministic) polynomial time", problems where the
solution can be found (searched for) in polynomial time.
So the distinction between P and NP is finding solutions vs.
checking a guessed solution.
Also, that "O(n) threshold" is wrong too. The corrent statement
is that if any NP-complete problems are in P, then NP=P,
i.e. searching for solutions is just as easy as checking them.
Most computer scientists find this highly unlikely, but no one
has proved it's impossible.
Papadimitriou (1994) is a nice, readable book on computational
complexity theory --- I recommend it.
Finally, the "no free lunch" theorem has nothing to do with
either of these: it is a theorem that no search algorithm works
better than chance on all possible problems.
- Cris Moore, Santa Fe Institute moore@santafe.edu