RE (複雜度)

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

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