万维百科

RE (复杂度)

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

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

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

相关页面

参考资料

  1. ^ Complexity Zoo: Class RE

本页面最后更新于2021-07-10 18:51,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器