易解性

^[1]  易解性(tractability)一個非嚴格定義的直觀概念.指一類問題不僅在理論是能行可解的，而且在實際上也是可解的一種性質.這種問題有時也稱為可行的.依丘奇論題，一函數f是能行可計算的，是指存在一個圖靈機M來計算f，而對這種圖靈機的紙帶長度和運行時間都沒有任何具體的限制.實際的計算機卻對此二者都是有限制的.這就造成了能行可計算性與實際可計算性之間的差異.即有些能行可計算函數不一定是實際可計算的.例如:假定計算f(n)一3”的值需要3”步，而每一步需要1微秒時間來完成，那麼計算f (60) = 360將需要1. 3 X 10'3個世紀J可見，這種計算不是實際可行的，因此，可以認為f不是易解的.與可計算性一樣，要對易解性下一個嚴格的定義是非常困難的，依庫漢姆(Cobham,A.)和愛德蒙茨(Edmonds , J. )1965年的建議，在計算複雜性領域中，人們一般地將易解性同多項式時間可計算性等同起來(參見“庫克一卡普論題”).