Details

Autor(en) / Beteiligte

• Lischke, Gerhard

Titel

Towards the Actual Relationship Between NP and Exponential Time

Ist Teil von

• Mathematical logic quarterly, 1999, Vol.45 (1), p.31-49

Ort / Verlag

Berlin: WILEY-VCH Verlag Berlin GmbH

Erscheinungsjahr

1999

Link zum Volltext

Quelle

Wiley-Blackwell subscription journals

Beschreibungen/Notizen

• We consider the relationship between the computational complexity classes NP and EL (deterministic exponential linear time). Taking into account the inclusion or incomparability of these classes, the existence or nonexistence of immune sets in their differences, and the existence or nonexistence of sparse sets in the differences, there are exactly 24 different cases for their relationship. We show that 16 cases are impossible in the real nonrelativized world as well as in any relativized world. Each of the remaining 8 cases is realizable in appropriate relativized worlds. Further we examine which of the 8 cases is most probably for a random oracle.