易解性的词语属性

易解性的百科含义

易解性(tractability)一个非严格定义的直观概念.指一类问题不仅在理论是能行可解的，而且在实际上也是可解的一种性质.这种问题有时也称为可行的.依丘奇论题，一函数f是能行可计算的，是指存在一个图灵机M来计算f，而对这种图灵机的纸带长度和运行时间都没有任何具体的限制.实际的计算机却对此二者都是有限制的.这就造成了能行可计算性与实际可计算性之间的差异.即有些能行可计算函数不一定是实际可计算的.例如:假定计算f(n)一3”的值需要3”步，而每一步需要1微秒时间来完成，那么计算f }60) = 360将需要1. 3 X 10'3个世纪J可见，这种计算不是实际可行的，因此，可以认为f不...