難解性(intractability)可解的但又不是易解的一種性質。若一個問題是能行可解的，但又不是實際可解的，則稱之為難解的.可見，難解性也是一種非嚴格定義的直觀概念，依庫克一卡普論題，難解的問題就是指非多項式時間可解的能行可解問題。
基本介紹
- 中文名：難解性
- 外文名：intractability
難解性(intractability)可解的但又不是易解的一種性質.若一個問題是能行可解的，但又不是實際可解的，則稱之為難解的.可見，難解性也是一種非嚴格定義的直觀概念，依庫克一卡普論題，難解的問題就是指非多項式時間可解的能行可解問題.
比較簡單的一些可判定的難解問題是在20世紀60年代初發現的，但它們都是一些“人工製造”的問題.這種例子的比較自然的例子直到20世紀70年代初才獲得，其中，邁耶(Meyer,A.)和斯托克梅耶(Stokmeyer , L.)證明了帶平方的正規表達式的等價性問題是一個可判定的問題.但卻需要指數時間，從而這是難解的.另一個有趣的難解問題是普萊斯博格算術系統的判定問題，費希爾(Fisher,J. J. )和拉賓(Rabin, M. O.)於1974年證明了普萊斯博格算術系統的判定需要指數時間2 Zcn，因而也是難解的.
