Separability and one-way functions |
| |
| Authors: | Lance Fortnow John D Rogers |
| |
| Affiliation: | 1. Computer Science Department, University of Chicago, Chicago, 60637, IL, USA
2. School of CTI, DePaul University, Chicago, 60604, IL, USA
|
| |
| Abstract: | We settle all relativized questions of the relationships between the following five propositions: - P = NP.
- P = UP.
- P = NP $\cap$ coNP.
- All disjoint pairs of NP sets are P-separable.
- All disjoint pairs of coNP sets are P-separable.
We make the first widespread use of variations of generic oracles to achieve the necessary relativized worlds. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
