P=NP explained for children.

[Isaac]

No seriously, why can't I find this? I want Elmo to come out and explain this to me. ★■◆● terminology.

You have buckets with various fruit. Now explain. Thank you!

[sdfgeoff]

My understanding:

NP-complete:
A problem in which there is no way to find an optimal solution except by trying each possible solution and seeing which is best.
It is not like linear algebra or even polynomial algebra where there are a finite number of solutions. In a NP-complete problem there is no definite solution, only comparisons of this one being "better"

Examples:
Buckets of fruit - um, not sure if this qualifies, but finding the tastiest apple. You have to take out all the fruit, identify it as an apple, evaluate it's colour, freshness and so on before you can chose the best.
AI programming - An AI has to choose which of it's enemies to shoot. To do this it iterates through all enemies, finds the distance, angle health etc and then picks the one it can get to fastest with the least health

Often in programming NP-complete problems are evaluated as floating point numbers added, multiplied etc together. Then these end numbers are compared to find the highest or lowest.

P Problems:
Have definite answers that can be solved mathematically.

Examples:
Buckets of fruit - Like finding the ratio of apples to pears. Or the percentage of oranges in a bucket. You take the total number and blaugh.....
Solving a complex math equation


In short "P" has definite answers, and can often be solved easily and quickly.
And "NP-complete" problems have relative answers, some are "better" To solve you have to find all the solutions and compare them.

[Isaac]

I like this answer! Thank you!

[sdfgeoff]

No probs (NP?)

[Sirius]

Strictly speaking, not all NP-complete problems require you to try all the alternatives to choose an optimal one, but they do tend to come down to something as inefficient/unscalable as that at some level. For instance, if you were trying to navigate from one side of Los Angeles to the other using the fastest route - that's an NP-complete problem - but obviously you can immediately rule out any dead ends (except those containing the origin or destination).

However, there is still no algorithm that can always, 100% of the time, tell you whether the quickest route from your current position will be down road A or B, in all situations (not just special cases like dead ends or loops), without solving the whole problem first. There are good guesses, but there is always a scenario where that guess will be wrong.

Edit: So, I guess, simplifying it; you can rule out some options in an NP-complete problem, but there is no known general case solution that doesn't ultimately result in evaluating all remaining solutions to find the best.

[Jeff250]

Isn't that just shortest path, which is in P? I suppose you should technically define the problem.

[Jeff250]

And in any case, regarding the subject, the dilemma is P vs. NP, not N vs. NP.

[Sirius]

May have been thinking of travelling salesman...

And I think it's short for polynomial/non-polynomial, right? So it would require a complex enough problem space to have O(n!) solutions in the first place, including the optimal one. So not factorising primes either, even though that can also get intractable once the numbers get large enough.

[Jeff250]

Nondeterministic polynomial time--the idea is that if there exists some algorithm where if you can somehow magically compute all branches simultaneously, then the algorithm only takes polynomial time.

Intuitively, NP is the set of problems that, if the answer to the problem is "yes," then you can generate a "certificate" so that someone can take the certificate and "prove" in polynomial time whether your answer is correct. You can think of the certificate as which branches you should take. (It can be less than that though; for instance, all P problems are trivially in NP, since the certificate can be nil, and proving it is just solving the problem itself.) Most people think that P is a strict subset of NP, but this has never been proven.

NP-hard problems are problems that most people think are more difficult than P problems (but again nobody can prove it). Formally, a problem X is NP-hard if there is a polynomial time Turing reduction from Circuit Satisfiability to X. In other words, if we can call X as a subroutine to solve Circuit Satisfiability in only a polynomial amount of additional time, then X is NP-hard. This sounds difficult to show, but by transitivity, if you can show a polynomial time reduction from *any* NP-hard problem to X, then X is NP-hard. We define NP-hardness like this because we want the property that if *any* NP-hard problem is in P, then they *all* are.

NP-complete problems are problems that are both in NP and NP-hard. Solving them from scratch is as hard as Circuit Satisfiability but, if the answer is "yes," then you can create a certificate so that someone can check the answer in polynomial time. For instance, consider Subset Sum:

Subset Sum
Input: a list of integers L and an integer k
Output: "yes" if some subset of integers in L sums to k; "no" otherwise

Determining from scratch whether such a subset exists seems difficult, about as difficult as summing each subset of L (at the very least, one can prove that it is as difficult as Circuit Sat). But, if the answer is "yes," we can generate a certificate that requires only polynomial time to verify: the subset of integers that sum to k.

It's tempting to say that that NP-complete problems require exponential time, since this is what most people conjecture, but if you can prove this, then you are rolling in dough, since P vs. NP is a pending million dollar problem. In other words, if you can prove either P = NP or P != NP, then you get a million bucks.

[Jeff250]

I suppose I failed to give an Elmo explanation using buckets of fruit.

Suppose you wanted to steal fruit, and each fruit has a different integral mass (say, in grams) but your bucket could only hold so many grams of mass.

NP-Hard: Determining which fruit you should steal and put in your bucket to optimize the amount of grams of fruit you can steal.
NP-Complete (so NP-Hard and NP): Determining whether there are fruit to steal that will completely fill your bucket to exact capacity.
P: Verifying that all of the fruit in your bucket completely fill it to exact capacity.

[snoopy]

So, I'm taking this heavy-duty statistics course right now for my EE degree....

I bet there are all sorts of cool statistical ways to solve NP-complete problems quickly and spiffaly. That being said, I probably can't help you... considering the fact that I'm just barely keeping up with what's going on in the class. I think that if you integrate the right things in the right way, you can probably get a really quick, correct answer.

[Isaac]

I suppose I failed to give an Elmo explanation using buckets of fruit.

Suppose you wanted to steal fruit, and each fruit has a different integral mass (say, in grams) but your bucket could only hold so many grams of mass.

NP-Hard: Determining which fruit you should steal and put in your bucket to optimize the amount of grams of fruit you can steal.
NP-Complete (so NP-Hard and NP): Determining whether there are fruit to steal that will completely fill your bucket to exact capacity.
P: Verifying that all of the fruit in your bucket completely fill it to exact capacity.

THANK YOU!!

[Jeff250]

I bet there are all sorts of cool statistical ways to solve NP-complete problems quickly and spiffaly.

Right, in cases where you don't mind a small chance of getting the wrong answer. If you want to have > 1/2 probability of success on any input, most people think you're still stuck in exponential time though, just not as bad exponential time as with a deterministic algorithm.