Former DeepMind Scientist Argues AlphaGo Solved NP-Hard Problem in Disturbing Way

Zhang argues AlphaGo's ability to compress what should be an intractable computational search into a small neural network represents a fundamental challenge to computer science's understanding of computational complexity. He suggests problems proven to be NP-hard in worst-case scenarios may be tractable in practice through neural networks that identify macroscopic structure, with implications extending to protein folding and weather prediction. This pattern—observable in AlphaFold and AlphaTensor—suggests certain problems assumed computationally intractable may yield to remarkably small amounts of compute.