跳转到内容

RE (复杂度)

维基百科,自由的百科全书

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

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

RE里面的每个成员都属于递归可枚举集合,因此同时也是丢番图集

相关页面

参考资料

  1. ^ Complexity Zoo: Class RE