| 关于相对化的P与NP问题的若干研究 |
| |
| 引用本文： | 宋恩民,黄文奇.关于相对化的P与NP问题的若干研究[J].华中科技大学学报(自然科学版),1994(6). |
| |
| 作者姓名： | 宋恩民 黄文奇 |
| |
| 作者单位： | 华中理工大学计算机科学与工程系 |
| |
| 基金项目： | 国家自然科学基金,华中理工大学青年自然科学研究基金 |
| |
| 摘 要： | 研究相对化的Ｐ＝？ＮＰ问题，提出了矛盾天书、相对天书和绝对天书的概念，证明了这些天书的客观存在性，并具体地构造了一个矛盾天书和一个ＮＰ集类之外的相对天书．结论对利用现有关于相对化Ｐ＝？ＮＰ问题的成果来研究ＮＰ问题将产生有益的影响
|
| 关 键 词： | 相对化 NP问题 相对天书 矛盾天书 绝对天书 |
Investigations on the Relativized P and NP Problem |
| |
| Song EnminDept.of Computer Sci.& Engin.,H. U. S.T.,Wuhan ,China
,Huang Wenqi.Investigations on the Relativized P and NP Problem[J].JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE,1994(6). |
| |
| Authors: | Song EnminDeptof Computer Sci& Engin H U ST Wuhan China Huang Wenqi |
| |
| Institution: | Song EnminDept.of Computer Sci.& Engin.,H. U. S.T.,Wuhan 430074,China
,Huang Wenqi |
| |
| Abstract: | The relativized P=?NP problem is investigated. The concepts of the relative oracle,contradictory oracle and independent oracle are proposed.It is proved that there exist suchoracles. A specific contradictory oracle and a relative oracle beyong the NP class are con-structed.The results may be helpful to investigations on the p=?NP problem using thoseof the relativized P and NP problem. |
| |
| Keywords: | relativization NP problem relative oracle contradictory oracle independent oracle |
| 本文献已被 CNKI 等数据库收录！ |
