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} ≠ NPA ≠ co-NPA 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, (), 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, (), 21-39
[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 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.