Premium
Towards the Actual Relationship Between NP and Exponential Time
Author(s) -
Lischke Gerhard
Publication year - 1999
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19990450104
Subject(s) - mathematics , oracle , exponential function , exponential growth , discrete mathematics , combinatorics , computer science , mathematical analysis , software engineering
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.