对于B存在A使P~A=NP~B成立的充要条件

Baker等人首先对P=?NP问题进行了相对化研究,获得了深刻的结果。本文对于任意语言B,讨论了存在语言A使P~A=NP~B成立的充要条件。 我们采用Cook的带oracle的图灵查询机器为我们的计算模型,有关查询机器的详细描