News for hackers. Stuff that matters.

A comment on P is not equal to NP. Parent comment

Re:P is not equal to NP by dgordon on Thursday October 30, 2008 @03:23PM (#349045)
What are the units? 10^14 is indeed far too much if it's seconds, but might not be beyond reason for a set of size 10 million if it's nanoseconds (then you have a bit under three hours.) So think about which units this would actually have.

Indeed, an algorithm being in P may not be sufficient to scale, but if a problem is NP-complete (assuming P != NP) there's almost certainly no scalable algorithm for it.

[ Parent | on HN ]
Re:P is not equal to NP by Retric on Monday November 03, 2008 @04:00PM (#352524)
(10^14) nanoseconds = 1.1574 days

I should have said If N^2 means 10 million... Anyway, I tend to think of 10^10 nanoseconds as vary bad (10 seconds) and (10^14) > 1 day as unreasonable, but that's just a rule of thumb from the days of 1Ghz CPUS's.

[ Parent | on HN ]