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