zbMATH — the first resource for mathematics

Average case completeness. (English) Zbl 0825.68420

68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Ben-David, S.; Chor, B.; Goldreich, O.; Luby, M., On the theory of average case complexity, (), 204-216
[2] A. BLASS, Private communication.
[3] Bollobas, B.; Fenner, T.I.; Frieze, A.M., An algorithm for finding Hamilton cycles in a random graph, (), 430-439
[4] S. BEN-DAVID AND M. LUBY, Private communication.
[5] Ben-David, S.; Chor, B.; Goldreich, O.; Luby, M, On the theory of average case complexity, (), 204-216
[6] Constable, R.L.; Hunt, H.B.; Sahni, S.K., On the computational complexity of scheme equivalences, () · Zbl 0447.68038
[7] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman New York · Zbl 0411.68039
[8] Gurevich, Y., Complete and incomplete randomized NP problems, (), 111-117
[9] Gurevich, Y., The challenger-solver game: variations on the theme of P=?NP, Bull. eur. assoc. theoret. comput. sc., oct., (1989) · Zbl 0759.68035
[10] Gurevich, Y.; Cauley, D.M., Average case complete problems, (April 1987), Unpublished manuscript
[11] Gurevich, Y.; Shelah, S., Expected computation time for Hamiltonian path problem, SIAM J. comput., 16, No. 3, 486-502, (1987) · Zbl 0654.68083
[12] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[13] Johnson, D.S., The NP-completeness column, J. algorithms, 5, 284-299, (1984) · Zbl 0546.68025
[14] Ko, Ker-I, On the definition of some complexity classes of real numbers, Math. systems theory, 16, 95-109, (1983) · Zbl 0529.03016
[15] P. G. KOLAITIS AND M. Y. VARDI, The decision problem for the probabilities of higher-order properties, in “STOC 1987.”
[16] Levin, L., Average case complete problems, SIAM J comput., 15, 285-286, (1986) · Zbl 0589.68032
[17] L. LEVIN, Private communication.
[18] Lewis, H.R., Complexity results for classes of quantificational formulas, J. comput. system sci., 21, 317-353, (1980) · Zbl 0471.03034
[19] Megiddo, N.; Vishkin, U., On finding a minimum dominating set in a tournament, IBM research report RJ 5745, (July 1987)
[20] Megiddo, N., Are the vertex cover and the dominating set problems equally hard?, IBM research report RJ 5783, (August 1987)
[21] Dinh Dieu, P.; Long Thanh, L.; Tuan Hoa, L., Average polynomial time complexity of some NP-complete problems, Theoret. comput. sc., 46, 219-237, (1986) · Zbl 0623.68039
[22] Venkatesan, R.; Levin, L., Random instances of a graph coloring problem are hard, ()
[23] Wilf, H.S., Some examples of combinatorial averaging, Amer math. monthly, 92, 250-261, (1985) · Zbl 0579.60008
[24] Zvonkin, A.K.; Levin, L., The complexity of finite objects and the algorithmic concepts of information and randomness, Russian math. surveys, 25/26, 83-124, (1970) · Zbl 0222.02027
[25] Impagliazzo, R.; Levin, L., No better ways to generate hard instances than picking uniformly at random, Focs, 812-821, (1990)
[26] A. Blass and Y. Gurevich, On the reduction theory for average case complexity, in “4th Workshop on Computer Science Logic” (E. Börger et al), Springer Lecture Notes in Computer Science, to appear. · Zbl 0789.68068
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.