关于复杂性类的限制相对化  

作　　者：李宏宙[1] 

机构地区：[1]华南师范大学计算机科学系,广州510631

出　　处：《中国科学（A辑）》1995年第10期1101-1106,共6页Science in China(Series A)

基　　金：国家"八六三"高科技计划资助项目

摘　　要：研究了复杂性类的两种类型的限制相对化:限制访问Oracle的查询次数和限制访问Oracle的类型.提出了Few算子和强Few算子并利用Few算子和强Few算子得到了这两种限制相对化的新特征.利用这种新特征给出了一个一般性的时间谱系崩溃结果,它推广、加强了原有的时间谱系崩溃结果.利用这种新特征进一步深刻地研究了概率多项式时间复杂性类PP的能力.

关 键 词：可计算复杂性 限制相对比 Few算子 S-F算子 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]