= 27d567bc2d48d9f40e9ccc20ea370b15)
army1987 comments on GAZP vs. GLUT - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (166)
Unless for any NP problem there exists an algorithm which solves it in just O(N^300) time.
NP=P is not the same as NP=Small P
Likewise, EXPTIME doesn't mean Large EXPTIME -- an algorithm running in exp(1e-15*N) seconds is asymptotically slower than one running in N^300 seconds, but it is faster for pretty much all practical purposes.
I once read an Usenet post or Web page along the lines of “There are two kinds of numbers: those smaller than Graham's number and those larger than Graham's number. Computational complexity theory traditionally only concerns itself with the latter, but only the former are relevant to real-world problems.”
No, slower. N^300 is polynomial, exp(1e-15*N) is exponential.
Maybe it's easier to understand them if you take log ? log(N^300) = log(N) * 300 and log(exp(1e-15 * N)) = 1e-15 * N
Whatever >0 multiplicative constants a and b you put, a * N will at one point become bigger (so, slower) than b * log(N). In this, that'll happen roughly when N will be somewhat above 10^15, around 10^20 according to a simple guess.