Immunity, simplicity, probabilistic complexity classes and relativizations

References

• Adleman , L. and Mander , K. 1977 . 9th Ann., Acm. Symp. on Theory of Computing . Reducibility, randomness and intractibility . 1977 , Boulder, Colo. pp. 151 – 153 .
   Google Scholar
• Baker , T. , Gill , J. and Solovey , R. 1975 . Relativization of the P = ?NP question . SIAM. J. Comput. , 4 : 431 – 442 .
   Google Scholar
• Balcázar , J. L. 1985 . Simplicity, relativizations and nondeterminism . SIAM. J. Comput. , 14 : 148 – 157 .
   Google Scholar
• Bennett , C. H. and Gill , J. 1981 . Relative to a random oracle A P A ≠ NP A ≠ co-NP A with probability 1 . SIAM. J. Comput. , 10 : 96 – 113 .
   Google Scholar
• Gill , J. 1977 . The complexity of probabilistic Turing Machins . SIAM. J. Comput. , 6 : 675 – 695 .
   Web of Science ®Google Scholar
• Ko , K. and Moore , D. 1981 . Completness, approximation and density . SIAM. J. Comput. , 10 : 787 – 796 .
   Google Scholar
• Xiang , Li . 1985 . On relativized nondeterministic polynomial time bounded computations . Intern. J. Computer Math. , 17 : 151 – 154 . Section A
   Web of Science ®Google Scholar
• Rackoff , C. 1982 . Relativized question involving probabilistic algorithms . J. ACM , 29 : 261 – 268 .
   Google Scholar
• Schöming , U. and Book , R. V. 1984 . Immunity, relativizations and nondeterminism . SIAM. J. Comput. , 13 : 329 – 337 .
   Google Scholar
• Soare , R. I. 1978 . Recursively enumerable sets and degree . Bull. of the Amer. Math. Soc. , 84 : 1149 – 1181 .
   Google Scholar
• Valiant , L. 1976 . Relative ccomplexity of checking and evaluating . Inf. Proc. , 5 : 20 – 23 .
   Google Scholar