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

【文件属性】：
文件名称：关于相对化的P=?NP问题的注记 (1993年)
文件大小：401KB
文件格式：PDF
更新时间：2021-05-24 05:04:10
自然科学 论文 问题P=?NP在相对化后随外部信息集的下同可能有相反的答案C7本文得出如下进一步的结果：1.存在着无穷个集合SI.Sz.这些集合的复杂度依次严格上升,并且在它们分别地作为外部信息集合,能文替地使命题P=NI'和1'*Nl'相对比,2.存在着在NP类之外的递归集A,使得P=NP等价于州=NI。