关于相对化的P=?NP问题的注记 (1993年)

【文件属性】：

文件名称：关于相对化的P=?NP问题的注记 (1993年)

文件大小：401KB

文件格式：PDF

更新时间：2024-06-12 22:50:50

自然科学 论文

问题P=?NP在相对化后随外部信息集的下同可能有相反的答案C7本文得出如下进一步的结果：1.存在着无穷个集合SI.Sz.这些集合的复杂度依次严格上升,并且在它们分别地作为外部信息集合,能文替地使命题P=NI'和1'*Nl'相对比,2.存在着在NP类之外的递归集A,使得P=NP等价于州=NI。