alt Hacker NewsSure 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.
Replies
testaccount28 • today at 5:03 AM
nah dude. i'll allow any finite size lookup table, but not an infinite one.
luc4 • today at 8:02 AM
Congrats, you just solved P=NP.
adgjlsfhk1 • today at 6:13 AM
no it doesn't. making the table takes O(2^n) time
> Sure but 2^n space complexity to get O(1) time complexity works for all n even infinite.
That's just incorrect. Are you assuming the table starts pre-filled, and has O(1) lookup? Nobody is using a model like that for this problem.
2^n space complexity doesn't automatically mean you get to fill that space with 2^n chosen computed values for free.
There's models with "oracle"s for various sub-problems and such (that's essentially what you're describing as the ability you're baking in to your model of computation, it can look up the answer to any multiplication for free), but that's not an interesting model for this problem.
If you do that you're just asking "hey, how long does it take to multiply two numbers if multiplying two numbers is free". Boring question, and not the one anyone else is asking.