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