難解性

難解性(intractability)可解的但又不是易解的一種性質。若一個問題是能行可解的,但又不是實際可解的,則稱之為難解的.可見,難解性也是一種非嚴格定義的直觀概念,依庫克一卡普論題,難解的問題就是指非多項式時間可解的能行可解問題。

基本介紹

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

相關詞條

熱門詞條

聯絡我們