Publication Details
Title: The Quality of Separation Between NP and Exponential Time; Reducing the Cases
Author: G. Lischke
Group: ICSI Technical Reports
Date: April 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-027.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-92-027
Bibliographic Reference:
G. Lischke. The Quality of Separation Between NP and Exponential Time; Reducing the Cases. ICSI Technical Report TR-92-027, April 1992
Author: G. Lischke
Group: ICSI Technical Reports
Date: April 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-027.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-92-027
Bibliographic Reference:
G. Lischke. The Quality of Separation Between NP and Exponential Time; Reducing the Cases. ICSI Technical Report TR-92-027, April 1992