相对于单元素语言的多项式时间谱系的研究

摘要：

通过讨论相对于单元素语言的多项式时间谱系,得到了Ⅱp1(A)∈△1的一个充分条件,进而研究了多项式时间谱系中的类∑p1内的单元素语言T与计算复杂性理论中的重要相对化语言类CO-NP(T)、P(NP)、∑p t-1(T)、△p1、NP(T)、NP等之间的联系。

关键词： 图灵机 多项式时间谱系 单元素语言 计算复杂性

作者: 李雅瑞

作者单位: 桂林空军学院,桂林,541003

会议类型: 国内会议

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

会议地点: 西安

会议语种:中文

页码: 48-49,202

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