<p>Assuming some background in mathematics,  how would you give a general overview of computational complexity theory to the naive?</p>

<p>I am looking for an explanation of the P = NP question.  What is P?  What is NP? What is a NP-Hard?</p>

<p>Sometimes Wikipedia is written as if the reader already understands all concepts involved.</p>

Unfortunately, the best two books I am aware of (
Garey and Johnson
and
Hopcroft and Ullman
) both start at the level of graduate proof-oriented mathematics.  This is almost certainly necessary, as the whole issue is very easy to misunderstand or mischaracterize.  Jeff
nearly got his ears chewed off
when he attempted to approach the matter in too folksy/jokey a tone.
Perhaps the best way is to simply do a lot of hands-on work with big-O notation
using lots of examples and exercises
.  See also
this answer
.  Note, however, that this is not quite the same thing: individual algorithms can be described by asymptotes, but saying that a
problem
is of a certain complexity is a statement about
every possible algorithm
for it.  This is why the proofs are so complicated!