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

What was said

"A 10-layer neural network can only do 10 sequential steps of thinking, right? 10 steps of neural network, parallelized, distributed representation thinking is able to amortize and approximate to a very, very high fidelity a nearly intractable search problem. It actually makes me wonder if our understanding of problems like P NP or these very fundamental computational hardness problems are incomplete."

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.