易解性(tractability)一个非严格定义的直观概念.指一类问题不仅在理论是能行可解的，而且在实际上也是可解的一种性质.这种问题有时也称为可行的.依丘奇论题，一函数f是能行可计算的，是指存在一个图灵机M来计算f，而对这种图灵机的纸带长度和运行时间都没有任何具体的限制.实际的计算机却对此二者都是有限制的.这就造成了能行可计算性与实际可计算性之间的差异.即有些能行可计算函数不一定是实际可计算的.例如:假定计算f(n)一3”的值需要3”步，而每一步需要1微秒时间来完成，那么计算f (60) = 360将需要1. 3 X 10'3个世纪J可见，这种计算不是实际可行的，因此，可以认为f不是易解的.与可计算性一样，要对易解性下一个严格的定义是非常困难的，依库汉姆(Cobham,A.)和爱德蒙茨(Edmonds , J. )1965年的建议，在计算复杂性领域中，人们一般地将易解性同多项式时间可计算性等同起来(参见“库克一卡普论题”).