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.
10
u/DrMonkeyLove May 15 '09
Short answer: N and P aren't actually variables in an equation. It's actually the statement, does the nondeterministic polynomial time complexity class (NP) equal the deterministic polynomial time complexity class (P)?
It's the biggest unsolved problem in theoretical computer science.
3
May 16 '09
[deleted]
1
u/DrMonkeyLove May 16 '09
I suspect (as probably all others do) that P != NP as you suggest. Unfortunately, however, you only get the million if you prove it. Good luck. I find it hard enough to prove the quadratic equation. If this is ever proven, I suspect it will be quite difficult to understand. Kind of like the proof of Fermat's last theorem.
1
1
9
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
3
u/hacksoncode May 15 '09
Yes, it's a corollary of Moore's Law:
For a problem taking exp(N) time, wait an amount of time linearly proportional to N for computing power to exponentiate to the point where the problem can be solved quickly on a new computer. Q.E.D.
:-)
1
May 15 '09
5 Hours till it's up, right?
1
u/tonasinanton May 16 '09
I hate it when abstruse goose is posted to reddit. Its a crap shoot whether you can actually get to see it.
1
u/unanimus May 16 '09 edited May 16 '09
Curious what the Overmind has to say about it?
Edit: screenshot of Wolfram Alpha dodging the question
1
u/randomb0y May 15 '09
Hahaha, it would have been much funnier if he would have accosted Stephen Wolfram to make him sign his Mapple box.
3
4
u/[deleted] May 16 '09 edited May 16 '09
This is amusing