The Quality of Separation Between NP and Exponential Time; Reducing the Cases
| Title | The Quality of Separation Between NP and Exponential Time; Reducing the Cases |
| Publication Type | Technical Report |
| Year of Publication | 1992 |
| Authors | Lischke, G. |
| Other Numbers | 732 |
| Abstract | We consider three aspects of quality of separation between complexity classes: inclusion, immunity and sparseness in the differences. These aspects are discussed in general and investigated especially for the relationship between NP and deterministic exponential linear time, where we can reduce the number of possible cases from 24 to 8. Seven of the 8 cases are realizable in appropriate relativized worlds; one case remains open. Also, we found an error in former papers on this subject. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-92-027.pdf |
| Bibliographic Notes | ICSI Technical Report TR-92-027 |
| Abbreviated Authors | G. Lischke |
| ICSI Publication Type | Technical Report |