宋恩民,金人超,黄文奇.关于相对化的P=?NP问题的注记[J].数学研究及应用,1993,13(3):443~450
关于相对化的P=?NP问题的注记
Note on the P =?NP Problem Relativized
投稿时间:1991-03-11  
DOI:10.3770/j.issn:1000-341X.1993.03.023
中文关键词:  
英文关键词:
基金项目:国家自然科学基金资助项目.
作者单位
宋恩民 华中理工大学计算机系 
金人超 华中理工大学计算机系 
黄文奇 华中理工大学计算机系 
摘要点击次数: 1383
全文下载次数: 886
中文摘要:
      问题P=?NP在相对化后随外部信息集的不同可能有相反的答案.本文得出如下进一步的结果:1.存在着无穷个集合S1,S2,…,这些集合的复杂度依次严格上升,并且在它们分别地作为外部信息集合,能交替地使命题P=NP和P≠NP,相对比;2.存在着在NP类之外的递归集A,使得P=NP等价于PA=NPA.
英文摘要:
      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 S1,S2,…, 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 PA= NPA.
查看全文  查看/发表评论  下载PDF阅读器