在理论计算机科学中，根据渐近最坏时间计算复杂度，对各种计算问题的难度进行了大量分类。对于哪些问题“对人工智能来说很难”甚至“对人工智能来说不可能”，似乎没有任何类似的分析。这在某种意义上是相当合理的，因为大多数研究都集中在可以解决的问题上。我感兴趣的是相反的。我需要证明一个问题以证明人工智能“无法合理解决”？
许多论文都说类似的东西
人工智能使我们能够找到现实世界中 NP 完全问题实例的解决方案。
说这个而不是“...... PSPACE-complete questions”是否有理论上的、有原则的理由？AI 在 PSPACE-complete、EXPTIME-complete 或 Turing 完全问题上不起作用是否有某种意义？
我的想法答案是参考一篇论文，该论文表明人工智能不能用于基于理论或统计推理来解决特定类型的问题。不过，任何展示和证明“对 AI 来说太难”的基准的答案都是可以的（如果基准与复杂性和可计算性理论有关，则可以加分）。
如果这个问题总体上没有答案，那么关于特定技术的答案对我来说也会很有趣。
好问题！
这是人工智能研究人员长期讨论的话题。简短的回答是“我们真的不知道总体上哪些主题很难，但我们确实知道哪些我们还没有好的技术。”
让我们首先解释为什么 AI 不关心像 NP 完备性这样的计算复杂性概念。人工智能研究人员在 90 年代发现，大多数理论上计算困难的问题实际上在实践中根本不难！例如，众所周知，典型的 NP-Hard 问题布尔可满足性有困难实例，但在实践中，这些几乎从未出现。即使他们这样做了，我们通常也可以用最少的计算时间得到好的近似解。由于许多 AI 问题都可以简化为 SAT，因此该领域的整个领域只使用这些近似技术和求解器。有一个很好的，如果有点旧，调查在这里. 自 2008 年以来，情况只会变得更好。基本上，NP-Hard 的东西并不难。因此，最坏情况的复杂性可能是猜测哪些问题对 AI 来说难以解决的错误工具。
在规模的另一端，我们根据问题的“大”程度来判断主观复杂性。这已被证明是非常不可靠的。一个例子是围棋，直到 2010 年我才被告知“永远不会被人工智能解决”。显然，我们完全错了。我们只是还不知道使用哪种技术。另一个例子是语言。基于规则的 AI'ers 尝试了几十年，但收效甚微。概率方法在更短的时间内基本上达到了人类水平的性能。如果你在 1970 年代问一位研究人员，语言对 AI 来说是否困难，他们会说是，但他们错了。这与计算硬件的进步密切相关：40 年前看似浪费和缓慢的技术现在完全实用了。有时他们会很好地解决问题。
这部分与人工智能者并不真正了解或同意什么是智能或解决问题意味着什么的问题有关。一些 AI 者坚持认为语言真的很难，而且我们现在使用的系统并不能真正解决语言问题，他们只是在盲目猜测，而这些猜测恰好是正确的。在这种观点下，语言仍然是困难的。Fodor过去是这种观点的坚定支持者，他的著作是阅读它的好地方，但我仍然听到人们在最近的 2015 年 AI 会议上支持这样的观点。
现在通常认为很难的事情是建立一个好的通用智能，它整合了许多领域的知识，并且可以合理地通过像图灵测试这样的东西。然而，这里已经取得了一些进展（看看虚拟助手），一些 AI 专家认为这可能也没有我们想象的那么难。
所以，基本上，我们不知道什么是困难的，因为我们不知道什么时候有人会提出一种新的令人兴奋的技术来解决以前认为很难的问题，我们知道最坏情况的复杂性不是一个好的测量系统对于“智能”的要求，我们不知道智能到底是什么。