Positive Relativizations of Complexity Classes
Positive Relativizations of Complexity Classes
复制标题
复杂性类的正相对化
DOI：
--
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
R. V. Book
中科院分区：
文献类型：
--
作者：
A. Selman;Mei;R. V. Book
由于Baker、Gill和Solovay的工作[SIAM J. Comput.，4（1975），pp. 431-442]和其他人，它已经成为一个范式，重要的开放问题的复杂性类不相对化。本文开发的标准甲骨文机模型的限制，相比之下，积极的包含关系相对化。我们的结果是通过均匀模拟技术得到的。因此，新的预言机模型表现出与相应的非相对化设备相同的计算能力。
Due to the work of Baker, Gill and Solovay [SIAM J. Comput., 4 (1975), pp. 431–442] and others, it has become a paradigm that important open questions about complexity classes do not relativize. This paper develops restrictions of the standard oracle machine model for which, in contrast, positive inclusion relationships do relativize. Our results are obtained by uniform simulation techniques. As a consequence, the new oracle machine models exhibit the same computational power as do the corresponding nonrelativized devices.