Abstract

We consider the relationship between the computational complexity classes NP and EL . 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