多项式时间算法：以多项式作为时间复杂度。
容易求解的问题：有多项式时间算法。
费解的问题：中不存在多项式时间算法。
容易解决的问题。 排序、最小生成树、单源最短路径等
被证明的费解的问题。
一种是不可计算的，不存在求解算法，如kaddx第10个问题的丢番图方程是否有整数解
另一个有算法，但至少需要指数时间，或者指数空间，或者更长的时间或者更长的空间。带乘方运算的正则表达式的整体性，即在字母a上的带乘方运算的正则表达式r中，3360r=a*？ 这个问题至少需要指数空间。
找不到多项式时间算法，也不能证明是难解的问题。 汉密尔顿电路问题、货郎问题、背包问题等
9.2由所有多项式时间都能解决的问题构成的问题类称为p类。
定义9.3判定问题=d，y，在存在两个输入变量多项式时间算法a和多项式p的情况下，对于各自的实例id、iy，存在t、|t|p (且a对输入I和t输出”是”的情况下，多项式
由可以验证所有多项式时间的判定问题构成的问题类称为NP类。
多项式时间变换
如何比较两个问题的难度？
定义9.4判定问题1=d1、Y1、2=d2、Y2。 函数f:d1d2满足条件：时
(1) f可以用多项式时间计算，
)2)所有id1，iy1f ) I )对于y2，
f被称为1到2的多项式时间变换。