= 27d567bc2d48d9f40e9ccc20ea370b15)
Sniffnoy comments on Theists are wrong; is theism? - 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 (533)
This is mostly irrelevant, but think complexity theorists use a weird definition of exponential according to which GNFS might still be considered exponential - I know when they say "at most exponential" they mean O(e^(n^k)) rather than O(e^n), so it seems plausible that by "at least exponential" they might mean Omega(e^(n^k)) where now k can be less than 1.
EDIT: Nope, I'm wrong about this. That seems kind of inconsistent.
They like keeping things invariant under polynomial transformations of the input, since that's has been observed to be a somewhat "natural" class. This is one of the areas where it seems to not quite.
Hmm, interesting in the notation that Scott says is standard to complexity theory my earlier statement that factoring is "subexponential" is wrong even though it is slower growing than exponential. But apparently Greg Kuperberg is perfectly happy labeling something like 2^(n^(1/2)) as subexponential.