RE (複雜度)

维基百科,自由的百科全书
跳转至: 导航搜索

可計算性理論計算複雜度理論內,RE (Recursively Enumerable,參考遞歸可枚舉集合)是一個決定型問題複雜度類。裡面的問題,當答案是'yes'的時候可以使用圖靈機在有限的時間內運算。[1] 不大正式的說法是,當問題的答案是'yes',則存在一些方法可以在有限時間內決定。不過,如果這個問題的答案是"NO",那這個機器有可能永遠沒有辦法結束運算。RE 也可以視為存在一個將問題裡面'yes'的答案一一列舉出來的圖靈機(也就是這裡所說'可枚舉的'的意思)。

co-RE 則是所有RE語言其補集(complement)的總集合。 某種意義上我們可以說,co-RE包含的語言,其裡面的問題要證明為錯誤,只要有限的時間;但是可能要無限的時間,才能證明這問題正確。

RE裡面的每個成員都屬於遞歸可枚舉集合,因此同時也是丟番圖集

相關頁面[编辑]

不可判定問題列表

參考資料[编辑]

  1. ^ Complexity Zoo: Class RE