关于相对化的P=?NP问题的注记

Note on the P =?NP Problem Relativized

中文摘要:

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

英文摘要:

      The P =?NP problem relativized can have two opposite results with the difference of oracle sets. In this paper, we get the results as follows:1. There exists an infinite series of sets S₁,S₂,…, whose complexity is strictly in-creasing, and if they become oracles, they can make the P =?NP and P ≠NP relativized alternately.2. There exists recursive oracle A out of NP such that P = NP equals P^A= NP^A.