某些复杂性类的递归可表示性

摘要：

本文探讨了计算复杂性理论中一些重要语言类PP、ZZP、PSPACE-”A|A在PSPACE中是多项式图灵完全的”等的递归可表示性.若ZPP(符号略)NP为真包含,本文证明了谓词”L∈ZPP”、”L是NP中多项式图灵完全集”都是不可判定的.

关键词： 递归可表式性 计算复杂性 多项式图灵完全集

作者: 李雅瑞

作者单位: 桂林空军学院(桂林)

会议类型: 国内会议

会议名称: 2002年全国理论计算机科学学术年会

会议地点: 长沙

会议语种:中文

页码: 8-9

在线出版日期: 2002-10-01（万方平台首次上网日期，不代表论文的发表时间）