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

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