HN Explorer

P=NP

14 points by SeanLuke ↗ HN
Here is my proof that P=NP, or rather, that you can solve all O(2^n) time and space problems in O(n) time and space.

Moore's Law says that circuit density, hence memory and CPU speed, doubles roughly every 1.5 years.

Take a problem which takes 2^n time. There exist three constants, A, B, and C, such that you can do the following. First, wait for A x n years. Second, go to Best Buy (or whatever store exists after the alien invasion of 2092) and purchase the fastest computer you can buy with B dollars. Third, run the problem on the computer for C x n seconds. QED.

When I was a PhD student at Maryland I told this proof to the esteemed Bill Gasarch, a friend of mine. He spat out a bunch of "no, no, no, no," then paused for a second contemplatively, then more "no, no, no...". I'm certain that during that second pause he was thinking, "can I publish this?" I'm sure Bill will deny this. :-)

12 comments

[ 2.8 ms ] story [ 42.8 ms ] thread
JacobAldridge
Without being even remotely familiar with the math (or, really, even the question) behind the P!=NP discussion, doesn't your argument depend on Moore's Law?

And isn't Moore's Law an observation of technological development since 1958, rather than a Law of Physics or Math?

http://xkcd.com/605/

Edit: Obviously - glad to be proved wrong or shot down for not understanding the debate.

carbocation
You are correct. IMO Moore's is really an observation about the behavior of people producing technology under a system that rewards incremental improvement.
eru
Moore's law says that transistor count increases exponentially, and it gives the rate of increase.

You may find the exponential increase in other "system[s] that rewards incremental improvement." But the rate of increase is specific. Also, say, fuel economy in cars did not grow exponentially, also one might argue that it is part of a similar system.

(Or did (and does) it increase exponentially? Anyone having any data?)

jgrahamc
1. Moore's Law is not an axiom, it's an observation.

2. NP and O(2^n) problems are not the same so your 'proof' doesn't help

3. Your proof did, however, make me laugh for its ingenuity.

SeanLuke
> Moore's Law is not an axiom, it's an observation.

Look, a law's a law.

nudge
This is probably the least correct thing I've ever read.
nixy 

  a law's a law
That's an axiom, not a law.
nadam
I really think that P can be equal to NP, just the algorithm can be very chaothic, based on pseudonumber generators, and very-hard-to-analyze emerging behaviour. For others to have an initial 'feeling' on this, I've created a polynomial time algorithm which tries to find N/2 cliques in a graph: It is already true for this quite simple algorithm that analyzing the correctness of the algorithm is harder than creating the algorithm itself:

http://nadamhu.wordpress.com/2010/08/12/the-good-guys-and-ba...

Tichy
Fail

Edit: to explain, P=NP is not about physical time, it is about the number of steps of an algorithm. Hence computer speed has nothing to do with it.

Also Moore's Law is not actually a law.

I know it is just meant as a joke, but still - at least show an understanding of complexity theory before making jokes...

jacobolus
You forgot about the great hyperinflation of 2050. Your B dollars are worthless.
vessenes
I like this, not because it has any sort of formal relevance, but because it reminds me that for the last 40 years or so, (actually longer), we have been able to solve O(2^n) problems in O(n) time where time < 40 years. Nice!

Probably Bill was despairing of your future, and simultaneously admiring your devious cleverness, not dreaming of publishing. But I could be wrong! If we wait 40 years, we may have the answer to my hypothesis as well.