早期的人工智能系统展示了智能的组成部分，希望能够在更大的问题上迅速取得进展。但这种希望没有实现。像块世界这样的微观世界场景似乎很有希望的技术并没有扩展到现实世界的问题。计算机问题解决的数学理论称为“计算复杂性”，解释了为什么会出现这种情况。
在20世纪70年代早期，斯蒂芬库克，列昂尼德莱文和理查德卡普确定了一类计算问题，现在被称为‘ NP完全 ‘（‘非确定性多项式时间完成‘）。这些是计算机可以快速检查解决方案是否正确的问题，但是找到正确的解决方案似乎需要不可能的大量时间。“旅行推销员问题”是一个着名的例子：
推销员必须访问他车内的一些城市，最终回到原点。他的车只有一定量的燃料。是否有一条路线可以完成巡回演出而不会耗尽燃料？
我们似乎能够完成NP完全问题的最好方法是详尽地考虑所有可能的解决方案。如果我们的推销员必须访问七十个城市，他将不得不考虑更多的路线而不是宇宙中的原子。无论计算机变得多快，这种详尽的方法对NP完全问题都是不可行的。
不幸的是，对于人工智能研究人员来说，似乎他们感兴趣的每一个问题都证明是NP完全的（或更糟）。黄金时代停滞不前。