Some observations on the probabilistic algorithms and NP-hard problems. (English) Zbl 0483.68045


68Q25 Analysis of algorithms and problem complexity
68W99 Algorithms in computer science
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI


[1] Adleman, L.; Manders, K., Reducibility, randomness, and intractability, Ninth Annual ACM Symposium on Theory of Computing, 151-153 (1977)
[2] Bennett, C. H.; Gill, J., Relative to a random oracle A, \(P^A\) ≠ \(NP^A\) ≠ co-\(NP^A\) with probability 1, SIAM J. Comput., 10, 96-113 (1981) · Zbl 0454.68030
[3] Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6, 4, 675-695 (1977) · Zbl 0366.02024
[4] Karp, R. M., Reducibilities among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-104
[5] Karp, R.; Lipton, R., Some connections between nonuniform and uniform complexity classes, Twelfth ACM Symposium on Theory of Computing, 302-309 (1980)
[6] Miller, G. L., Riemann’s hypothesis and tests for primality, J. Comput. System Sci., 13, 300-317 (1976) · Zbl 0349.68025
[7] Pratt, V., Every prime has a succinct certificate, SIAM J. Comput., 4, 214-220 (1975) · Zbl 0316.68031
[8] Rabin, M. O., Probabilistic algorithms, (Traub, J. F., Algorithms and Complexity (1976), Academic Press: Academic Press New York), 21-39 · Zbl 0384.60001
[9] Rackoff, C., Relativized questions involving probabilistic algorithms, Proc. Tenth ACM Symposium on Theory of Computing, 338-342 (1978) · Zbl 1282.68158
[10] Simon, J., On some central problems in computational complexity (1975), Cornell University: Cornell University Ithaca, NY, TR 75-224
[11] Solovay, R.; Strassen, V., A fast Monte-Carlo test for primality, SIAM J. Comput., 84-85 (1977) · Zbl 0345.10002
[12] Stockmeyer, L. J., The polynomial time hierarchy, Theoret. Comput. Sci., 3, 1, 1-22 (1977) · Zbl 0353.02024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.