Hacker News new | past | comments | ask | show | jobs | submit login

who cares about P=NP when you can do that for $8000 ?



You are misunderstanding. P=NP is a theoretical, in some ways even a philosophical question about the limits of logic and knowledge. Many problems that are NP complete have algorithms to find almost perfect answers in polynomial time. P=NP is about knowing if you can find perfect answers.

Then, there are many problems out there which are not NP complete for which we are nowhere near to finding fast, accurate solutions. The problem is not that logic prevents us, but that we're simply not clever enough yet.

What I'm trying to say in a roundabout way is that spinning up many cores will not help you find a perfect, fast solution to an NP complete problem. And just because you have 10,000 cores that is not an indicator of it being difficult or hard to solve a given problem, regardless of its complexity class.


Because NP problems have exponential time growth.

Example: a brute-force attack of an encryption algorithm that uses a 256-bit-key, would require trying out all possible keys, which is 2^256 ... which right now it would take far longer than the age of the universe to complete.

AND, most importantly, dividing that number by 10,000 (the number of computers in the article), or heck, let's be generous and say we have 1,000,000,000 computers ... would be absolutely meaningless.

It's simple really -- 2^256 / 1 billion computers =~ 2^226 -- and computing it still takes far longer than the age of our universe.

And lets say that with technology advances, you can have 70,000,000,000 computers (that's 70 billion computers, or a 700,000,000 % increase from the number in our article). Nevermind the energy required to power them or the storage capacity needed, or other such none-sense. So instead of 2^226, you now have 2^220 cycles to go through, an absolutely meaningless decrease, and still takes far longer than the age of our universe.

As a fun exercise, try figuring out how many computers would be required to bring that number down to ~ 2^200 -- that would still take far longer than the age of our universe to compute ;)


Almost everyone. 2^n/1000 is still far slower than n^2 for n >= 19.


Thanks guys for telling me about P/NP

time for me to teach you something : http://en.wikipedia.org/wiki/Humour


Humour is pretty much seen as noise on Hacker News. If a joke also has some insight about the article, it will get upvotes, but if it's just a joke it gets downvoted.




Consider applying for YC's Summer 2025 batch! Applications are open till May 13

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: