论文部分内容阅读
问题P=?NP在相对化后随外部信息集的不同可能有相反的答案.本文得出如下进一步的结果:1.存在着无穷个集合S_1,S_2,…,这些集合的复杂度依次严格上升,并且在它们分别地作为外部信息集合,能交替地使命题P=NP和P≠NP,相对比;2.存在着在NP类之外的递归集A,使得P=NP等价于P~A=NP~A.