Re:A New Map Traces the Limits of Computation
by darkmighty on Wednesday September 30, 2015 @11:38AM
(#10304723)
is (1+o(1)) essentially anything subexponential but hyperpolynomial?
[ Parent
| on HN ]
Re:A New Map Traces the Limits of Computation
by thomasahle on Wednesday September 30, 2015 @02:08PM
(#10305879)
Yeah anything subexponential. We can also write it as `2^o(n)`.
It doesn't have to by hyperpolynomial, if you solve ETH in linear time, you also refute it :-)