The real difficult part of explaining this concept to the layperson is getting them to understand what asymptotic complexity is. The example I always use when I explain this to people with little or no math or computer science background is sorting algorithms, explained using the following example of a deck of cards. Everybody's familiar with a deck of cards, and it doesn't take much more math than the most intuitive bits statistics.
Imagine I give you a deck of perfectly shuffled (i.e. uniformly distributed) cards, and decree that you need to find the ace of spades. What you have to do is go through each card one-by-one, and stop when you've found it. You'll have to look at, on average, 26 cards, since there are 52 cards in the deck, and each card has an equal chance of being the ace of spades. Now, let's say I add another 52 cards, this time with a defaced ace of spades, and wanted you to find the original (non-defaced) ace of spades, which is now just one card out of 104. On average, this'll take 52 cards.
Notice that when I double the amount of cards I gave you, the amount of work (that is, looking at cards) you had to do also doubles, meaning that for N cards, the amount of work is N/2. When the amount of work is directly related to the number of cards, excluding dividing or multiplying by a number that does not depend on the number of cards (in this example, dividing by 2), then we simplify things and say that this process for finding the Ace of Spades takes BigO(N) work to finish.
Now, imagine I give you that same deck, and instead of demanding that you find the ace of spades, I require you to sort it out into suits, with the cards in each suit in increasing order. One way to do this is to keep a separate pile for each suit, with that pile in increasing order. Deciding where to put the first card of each suit is easy, you just make a new pile for it. The later cards are not as easy, since you have to go through the pile and find the right place to put the new card.
Right away you can tell that this sorting takes more work from you than finding the ace of spades does. Instead of just looking at each card to see if it's the ace of spades, you first have to check the suit of the card to determine which pile it should go in. Then, you have to look through that pile for the proper place to insert the card. I won't go into the math, but it turns out the best way to sort a deck of cards into piles of suits[1] like this takes N * lgN work, where lgN is a fancy number that isn't constant, but gets bigger when N gets bigger, unlike the division by 2 in the ace of spades example. That means that sorting cards is harder than finding the ace of spades.
This business of determining how hard tasks like sorting cards are is called "analyzing the complexity" of a task. Except, instead of saying task, computer scientists like to say "function." The question of whether or not P = NP is a question about whether a certain kind of tasks called "deterministic Polynomial" tasks (which are referred to by the P) are as hard as another kind of tasks called "Non-deterministic Polynomial" tasks (referred to by the NP).
I have a second part that tries to explain the difference between determinism and non-determinism using a magic deck of cards where we can always draw the card that we want (the "magic" deck is, of course, merely a "non-deterministic" deck), but I've already spend an hour or so writing this first part up. I can post the second part of the explanation tomorrow, if folks are interested.
[1]: This is meant to be a memory constraint. Obviously, radix sort takes linear time too if the key sizes are constant, but has a memory overhead of N. As far as I'm aware–and please correct me if I'm wrong–the fastest sorting algorithms with constant memory overhead are comparison-based sorting algorithms, which take N lgN time. But, even if I am wrong, it's incidental to the main purpose of the explanation.
Imagine I give you a deck of perfectly shuffled (i.e. uniformly distributed) cards, and decree that you need to find the ace of spades. What you have to do is go through each card one-by-one, and stop when you've found it. You'll have to look at, on average, 26 cards, since there are 52 cards in the deck, and each card has an equal chance of being the ace of spades. Now, let's say I add another 52 cards, this time with a defaced ace of spades, and wanted you to find the original (non-defaced) ace of spades, which is now just one card out of 104. On average, this'll take 52 cards.
Notice that when I double the amount of cards I gave you, the amount of work (that is, looking at cards) you had to do also doubles, meaning that for N cards, the amount of work is N/2. When the amount of work is directly related to the number of cards, excluding dividing or multiplying by a number that does not depend on the number of cards (in this example, dividing by 2), then we simplify things and say that this process for finding the Ace of Spades takes BigO(N) work to finish.
Now, imagine I give you that same deck, and instead of demanding that you find the ace of spades, I require you to sort it out into suits, with the cards in each suit in increasing order. One way to do this is to keep a separate pile for each suit, with that pile in increasing order. Deciding where to put the first card of each suit is easy, you just make a new pile for it. The later cards are not as easy, since you have to go through the pile and find the right place to put the new card.
Right away you can tell that this sorting takes more work from you than finding the ace of spades does. Instead of just looking at each card to see if it's the ace of spades, you first have to check the suit of the card to determine which pile it should go in. Then, you have to look through that pile for the proper place to insert the card. I won't go into the math, but it turns out the best way to sort a deck of cards into piles of suits[1] like this takes N * lgN work, where lgN is a fancy number that isn't constant, but gets bigger when N gets bigger, unlike the division by 2 in the ace of spades example. That means that sorting cards is harder than finding the ace of spades.
This business of determining how hard tasks like sorting cards are is called "analyzing the complexity" of a task. Except, instead of saying task, computer scientists like to say "function." The question of whether or not P = NP is a question about whether a certain kind of tasks called "deterministic Polynomial" tasks (which are referred to by the P) are as hard as another kind of tasks called "Non-deterministic Polynomial" tasks (referred to by the NP).
I have a second part that tries to explain the difference between determinism and non-determinism using a magic deck of cards where we can always draw the card that we want (the "magic" deck is, of course, merely a "non-deterministic" deck), but I've already spend an hour or so writing this first part up. I can post the second part of the explanation tomorrow, if folks are interested.
[1]: This is meant to be a memory constraint. Obviously, radix sort takes linear time too if the key sizes are constant, but has a memory overhead of N. As far as I'm aware–and please correct me if I'm wrong–the fastest sorting algorithms with constant memory overhead are comparison-based sorting algorithms, which take N lgN time. But, even if I am wrong, it's incidental to the main purpose of the explanation.