| Popis: |
Two complexity classes are considered to be weakly separated if they are separated but there is no immune set in the difference of the classes. It is shown that the weak separation between NP and exponential time, together with the inclusion and the weak separation simultaneously in both directions (weak incomparability), is not possible in any relativized or nonrelativized world. On the other hand, a weak separation without inclusion and a strong-weak incomparability are realizable in relativized worlds. > |
