152P类与NP类问题 ·可由多项式时间算法求解的问题→易处理的问题 需要超多项式时间才能求解的问题→难处理的问题。 有许多问题,从表面上看似乎并不比排序或图的搜索等问题更 困难,然而至今人们还没有找到解决这些问题的多项式时间算 法,也没有人能够证明这些问题需要超多项式时间下界 在图灵机计算模型下,这类问题的计算复杂性至今未知 为了研究这类问题的计算复杂性,人们提出了另一个能力更强 的计算模型,即非确定性图灵机计算模型,简记为NDTM (Nondeterministic Turing Machine) ·在非确定性图灵机计算模型下,许多问题可以在多项式时间内 求解。10 15.2 P类与NP类问题 • 可由多项式时间算法求解的问题→易处理的问题， 需要超多项式时间才能求解的问题→难处理的问题。 • 有许多问题，从表面上看似乎并不比排序或图的搜索等问题更 困难，然而至今人们还没有找到解决这些问题的多项式时间算 法，也没有人能够证明这些问题需要超多项式时间下界。 • 在图灵机计算模型下，这类问题的计算复杂性至今未知。 • 为了研究这类问题的计算复杂性，人们提出了另一个能力更强 的计算模型，即非确定性图灵机计算模型，简记为NDTM (Nondeterministic Turing Machine)。 • 在非确定性图灵机计算模型下，许多问题可以在多项式时间内 求解