2.2　算法复杂性中的难解性问题

算法复杂性包括算法的空间以及时间两方面的复杂度问题，汉诺塔问题主要讲的是算法的时间复杂度。

关于汉诺塔问题算法的时间复杂度，可以用一个指数函数O(2n)来表示，显然，当n很大（如10 000）时，计算机是无法处理的。相反，当算法的时间复杂度的表示函数是一个多项式，如O(n2)时，则可以处理。因此，一个问题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将随n的增加而急剧增长，以致即使是中等规模的问题也无法求解，于是这一类问题被称为难解性问题。人工智能领域中的状态图搜索问题（解空间的表示或状态空间搜索问题）就是一类典型的难解性问题。

在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有在多项式时间内可以验证的问题称为NP类问题。由于P类问题采用的是确定性算法，NP类问题采用的是非确定性算法，而确定性算法是非确定性算法的一种特例，因此，可以断定P⊆NP。