摘要
研究了复杂性类的两种类型的限制相对化:限制访问Oracle的查询次数和限制访问Oracle的类型.提出了Few算子和强Few算子并利用Few算子和强Few算子得到了这两种限制相对化的新特征.利用这种新特征给出了一个一般性的时间谱系崩溃结果,它推广、加强了原有的时间谱系崩溃结果.利用这种新特征进一步深刻地研究了概率多项式时间复杂性类PP的能力.
出处
《中国科学（A辑）》
CSCD
1995年第10期1101-1106,共6页
Science in China(Series A)
基金
国家"八六三"高科技计划资助项目
