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

摘要：

@@ 1.引言
计算复杂性语言类的递归可表示性十分重要,Uwe Schoning在文[1]中研究了一些重要语言类,如P,NP,CO-NP等的递归可表示性,本文在此基础上进一步探讨计算复杂性理论中一些重要语言类PP、ZPP、PSPACE-{A |A在PSPACE中是多项式图灵完全的}等的递归可表示性.目前尚未知道ZPP∈NP是否是真包含,若为真包含,本文证明了谓词"L∈ZPP"、"L是NP中多项式图灵完全集"都是不可判定的.本文所引用的符号与文[2]一致.

机标关键词：递归、可表示性、计算复杂性理论、多项式图灵完全集、语言类、可判定、证明、谓词、基础、符号

所属期刊栏目：29

分类号：TP3;O17

在线出版日期：2005-04-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：8-9