RE (複雜度)

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

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

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

相關頁面

參考資料

  1. ^ Complexity Zoo: Class RE