RE (复杂度)

在可计算性理论跟计算复杂度理论内，RE（Recursively Enumerable，参考递归可枚举集合）是一个决定型问题的复杂度类。里面的问题，当答案是"yes"的时候可以使用图灵机在有限的时间内运算。^[1]不大正式的说法是，当问题的答案是"yes"，则存在一些方法可以在有限时间内决定。不过，如果这个问题的答案是"NO"，那这个机器有可能永远没有办法结束运算。RE也可以视为存在一个将问题里面"yes"的答案一一列举出来的图灵机（也就是这里所说'可枚举的'的意思）。

co-RE则是所有RE语言其补集（complement）的总集合。某种意义上我们可以说，co-RE包含的语言，其里面的问题要证明为错误，只要有限的时间；但是可能要无限的时间，才能证明这问题正确。