Immunity, simplicity, probabilistic complexity classes and relativizations

Abstract

Let R be random polynomial-time complexity class and UP be the class of sets accepted by polynomial-time NTMs which have an unique accepting path for each string they accept. Let R(A) be the relativization of these classes with respect to oracle A. Similarly, we define co-NP(A)NP(A)UP(A)P(A), and co-R(A). In this paper, we prove the following main results:

1. There exists a recursive oracle set A such that R(A) contains a P(A)-immune set.

2. There exists a recursive oracle set B such that R(B) contains a P(B)-immune set and NP(B) = R(B).

3. There exists an oracle set C such that NP(C) contains a R(C)-immune set and R(C) = P(C).

4. There exists a resursive oracle set D such that R(D) contains a simple set and NP(D) = R(D). We have the similar results for UP and ZPP = R ∩ co-R.

Keywords:

• Complexity classes
• probabilistic algorithms
• oracle turing machines
• relativization
• immunity
• simplicity
• NP R UP ZPP P

C.R. Categories:

• F.1.2
• F.1.3