|
|||||
|
|
| 关于复杂性类的限制相对化 | |
| 作者姓名： | 李宏宙 |
| 作者单位： | 华南师范大学计算机科学系 广州 510631 |
| 摘 要： | 研究了复杂性类的两种类型的限制相对化:限制访问Oracle的查询次数和限制访问Oracle的类型.提出了Few算子和强Few算子并利用Few算子和强Few算子得到了这两种限制相对化的新特征.利用这种新特征给出了一个一般性的时间谱系崩溃结果,它推广、加强了原有的时间谱系崩溃结果.利用这种新特征进一步深刻地研究了概率多项式时间复杂性类PP的能力. |
| 关 键 词： | 可计算复杂性 限制相对化 Few算子和Strong-Few算子 时间谱系 PP |
| 点击此处可从《中国科学A辑》浏览原始摘要信息 | |