• 0 Posts
  • 7 Comments
Joined 2 months ago
cake
Cake day: May 16th, 2025

help-circle


  • There’s really no good way to make any statements about what problems LLMs can solve in terms of complexity theory. To this day, LLMs, even the newfangled ā€œreasoningā€ models, have not demonstrated that they can reliably solve computational problems in the first place. For example, LLMs cannot reliably make legal moves in chess and cannot reliably solve puzzles even when given the algorithm. LLM hypesters are in no position to make any claims about complexity theory.

    Even if we have AIs that can reliably solve computational tasks (or, you know, just use computers properly), it still doesn’t change anything in terms of complexity theory, because complexity theory concerns itself with all possible algorithms, and any AI is just another algorithm in the end. If P != NP, it doesn’t matter how ā€œintelligentā€ your AI is, it’s not solving NP-hard problems in polynomial time. And if some particularly bold hypester wants to claim that AI can efficiently solve all problems in NP, let’s just say that extraordinary claims require extraordinary evidence.

    Koppelman is only saying ā€œcomplexity theoryā€ because he likes dropping buzzwords that sound good and doesn’t realize that some of them have actual meanings.





  • I know r/singularity is like shooting fish in a barrel but it really pissed me off seeing them misinterpret the significance of a result in matrix multiplication: https://old.reddit.com/r/singularity/comments/1knem3r/i_dont_think_people_realize_just_how_insane_the/

    Yeah, the record has stood for ā€œFIFTY-SIX YEARSā€ if you don’t count all the times the record has been beaten since then. Indeed, ā€œcountless brilliant mathematicians and computer scientists have worked on this problem for over half a century without successā€ if you don’t count all the successes that have happened since then. The really annoying part about all this is that the original announcement didn’t have to lie: if you look at just 4x4 matrices, you could say there technically hasn’t been an improvement since Strassen’s algorithm. Wow! It’s really funny how these promptfans ignore all the enormous number of human achievements in an area when they decide to comment about how AI is totally gonna beat humans there.

    How much does this actually improve upon Strassen’s algorithm? The matrix multiplication exponent given by Strassen’s algorithm is log4(49) (i.e. log2(7)), and this result would improve it to log4(48). In other words, it improves from 2.81 to 2.79. Truly revolutionary, AGI is gonna make mathematicians obsolete now. Ignore the handy dandy Wikipedia chart which shows that this exponent was … beaten in 1979.

    I know far less about how matrix multiplication is done in practice, but from what I’ve seen, even Strassen’s algorithm isn’t useful in applications because memory locality and parallelism are far more important. This AlphaEvolve result would represent a far smaller improvement (and I hope you enjoy the pain of dealing with a 4x4 block matrix instead of 2x2). If anyone does have knowledge about how this works, I’d be interested to know.