logoalt Hacker News

AnotherGoodName • today at 4:25 AM • 2 replies • view on HN

It’s unintentionally making a mockery of OpenAIs results by highlighting Blums speedup theorem in action. Namely that you can always reduce time complexity with a small move into space complexity.

That unintentional mockery of a repo is 262million lines of such moves and growing. I don’t think for a second anyone involved has a clue about complexity theory though or they’d just jump to the obvious “O(1) time complexity using an O(2^n) lookup table to cover all possible n bits of input” which is the final end state of Blums speedup theorem.


Replies

ashdksnndck • today at 8:07 AM

The input is unlimited size and the algorithm is achieving a speedup with constant size code.