如果你发现自己要解决的问题是NP完全问题，这就意味着传统意义上的计算机技术在解决该问题上是行不通的：从精准的数学意义来说，你的问题太难了。
NP完全问题的基本结构早在20世纪70年代就已成形。1971年美籍加拿大数学家斯蒂芬·库克(Stephen Cook)的一篇论文确定了NP完全问题的核心思想，随后美国人理查德·卡普(Richard Karp)证明了库克NP完全问题的范畴比最初想象的要广泛得多。整个20世纪70年代，人工智能领域的研究人员开始利用NP问题完全性理论来研究他们的课题，结果令人震惊。不管哪个领域——解决问题、玩游戏、计划、学习、推理任何方面——似乎关键性的问题都是NP完全问题(甚至更糟)。这种现象普遍得成了一个笑话——所谓的“AI完全问题”[3]意味着“一个和AI本身一样难的问题”，如果你能解决一个AI完全问题，你就能解决所有AI问题了。
发现你正在研究的问题是NP完全问题——或者更糟——真是个沉重的打击，在NP完全性理论及其论证结果被理解之前，人们总是希望出现重大突破使得这些问题变得简单——用术语来说就是易处理。从技术上讲，这种希望还是存在的，因为我们还没有明确地证明NP完全问题不可解。但到了20世纪70年代，NP完全性理论和组合爆炸成为笼罩在人工智能领域的阴影，以计算复杂性的形式阻拦在人工智能发展道路上，使它陷入停滞。黄金年代发展起来的技术似乎都无法扩大它们的使用范围，走不出玩具或者特定小世界(比如积木世界)的范畴。50到60年代过于乐观的预测遇到了现实难题，这让人工智能领域的先驱者们无比困扰。