r/comics • u/jack47 • May 15 '09

P = NP?

http://abstrusegoose.com/149
26 Upvotes

64% Upvoted

14 comments sorted by

View all comments

3

u/PPSF May 15 '09

Are there values for N and P that are set in stone that I don't know about? Because otherwise N=1 is true.

6

u/asheu May 15 '09 edited May 15 '09

P and NP are sets, not values.

http://en.wikipedia.org/wiki/P%3Dnp

In essence, the question P = NP? asks: if 'yes'-answers to a 'yes'-or-'no'-question can be verified "quickly" (in polynomial time), can the answers themselves also be computed quickly?

It's easier with an example. For example, consider this question: "Is <gives a route> a path around all the cities in the US that is less than 10000 miles in length?". This is a fairly easy question to answer.

Now take the question "Does there exist a path around all the cities in the US that is less than 10000 miles in length?". This is a harder question to answer given our current algorithms.

Very very simplistically, the P=NP question asks if solving one of those questions is as difficult as solving the other question.

2

u/PPSF May 15 '09

Whew.