3 ms·
There are plenty of algorithms with n^k where k>4, just not useful ones. Off the top of my head, checkout work by Eric D. Demaine. His work is on problems that
by spooningtamarin 11y ago
There are plenty of algorithms with n^k where k>4, just not useful ones.
Off the top of my head, checkout work by Eric D. Demaine. His work is on problems that seem very real, and solutions (algorithms) definitely show very lovely interaction of several different areas of research, problem solving skills at its finest.
http://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant http://cstheory.stackexchange.com/questions/6660/polynomial-...
- dllthomas 11y agoThanks! That weakens my speculation about human capabilities, though the fact that it deserves calling out as "problem solving skills at its finest" seems to leave me some wiggle room ;) To be honest, I'm not sure how to quantify the relative populations of higher-exponent and lower-exponent found algorithms, and if there is a skew some of that might well be due to the decreased attention to the space of higher exponent algorithms due to lower expected usefulness...