alt Hacker NewsThe whole point of this problem is that there are no bounds on integer size.
The whole point of complexity theory is that there are no bounds on input size.
The whole point of this problem is that there are no bounds on integer size.
The whole point of complexity theory is that there are no bounds on input size.
Sure but 2^n space complexity to get O(1) time complexity works for all n even infinite. Thats the end state of Blums speedup theorem in either direction and it doesn’t limit to any bounds. I just stating a limited of bounds above for the sake of giving understanding. Complexity theory doesn’t care that 2^n space complexity doesn’t work when n is infinite anymore than it cares that nlogn also doesn’t work when n is infinite. It’s not the point.