你不必为了得到一个难题而达到 EXP-complete。NP-Complete 已经够糟糕了……

密码学假设（例如，单向函数的存在）也是产生难题的好方法

在该领域进行了大量研究，例如学习布尔公式和有限自动机的密码学限制- DFA在多项式时间内不可学习PAC 。

但是，这些负面结果与编写出色的国际象棋程序之间存在重要区别。负面结果意味着对于给定的问题，没有算法可以解决所有实例（比如说，在多项式时间内）。这并不意味着您将无法在某些/大多数/所有情况下更好地发挥人类冠军。

请注意，这种复杂性观察与技术无关。机器学习只是解决这些问题的另一种（有用的）方法。

至于机器学习处理这些问题的能力，你可以在机器学习（SVM、神经网络、决策树）中到处发现 NP-Complete 问题。这并没有阻止他们找到许多有用的模型。