RE (複雜度) 在可計算性理論跟計算複雜度理論內RERecursively Enumerable參考遞歸可枚舉集合是一個決定型問題的複雜度類裡面的問題當答案是yes的時候可以使用圖靈機在有限的時間內運算不大正式的說法是當問題的答案是yes則存在一些方法可以在有限時間內決定不過如果這個問題的答案是NO那這個機器有可能永遠沒有辦法結束運算RE也可以視為存在一個將問題裡面yes的答案一一列舉出來的圖靈機也就是這裡所說可枚舉的的意思 coRE則是所有RE語言其補集complement的總集合某種意義上我們可以說coRE包含的語言其裡面的問題要證明為錯誤只要有限的時間但是可能要無限的時間才能證明這問題正確 RE裡面的每個成員都屬於遞歸可枚舉集合因此同時也是丟番圖集