|
|
| |
| THE STRUCTURE OF RELATIVIZED P AND NP QUESTIONS |
| |
Citation： |
Ye Hong.THE STRUCTURE OF RELATIVIZED P AND NP QUESTIONS[J].Chinese Annals of Mathematics B,1988,9(4):470~477 |
| Page view： 791
Net amount： 809 |
Authors： |
Ye Hong; |
|
|
| Abstract： |
First, based on the work of [5] a new property on the structure of P and NP is proved. Then, using the notions of mitotic and non-mitotic defined by R. E. Ladner, the
author defines similar concepts in the relativized classes $\[{P^X},N{P^X}\]$ and constructs a recursive oracle. In the constructions an NP-non-mitotic set is obtained by using the simple priority argument and the coding strategy which Robert I. Soare used to prove the density results in the r.e. degrees. |
Keywords： |
|
Classification： |
|
|
|
Download PDF Full-Text
|
|
|
|
