×
Gurevich, Yuri

Average case completeness. (English) Zbl 0825.68420

J. Comput. Syst. Sci. 42, No. 3, 346-398 (1991).

Cited in 1 Review
Cited in 46 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
Cite Review PDF
Full Text: DOI

References:

[1] Ben-David, S.; Chor, B.; Goldreich, O.; Luby, M., On the theory of average case complexity, (Proc. 21st Annual ACM Symposium on Theory of Computing, ACM (1989)), 204-216
[2] A. BLASS, Private communication.; A. BLASS, Private communication.
[3] Bollobas, B.; Fenner, T. I.; Frieze, A. M., An algorithm for finding Hamilton cycles in a random graph, (Proc. 17th Annual ACM Symposium on Theory of Computing, ACM (1985)), 430-439
[4] S. BEN-DAVID AND M. LUBY, Private communication.; 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, (Proc. 21st Symp. on Theory of Computing, ACM (1989)), 204-216
[6] Constable, R. L.; Hunt, H. B.; Sahni, S. K., On the Computational Complexity of Scheme Equivalences, (Report No. 74-201 (1974), Dept. of Computer Science, Cornell University: Dept. of Computer Science, Cornell University Ithaca, NY) · Zbl 0447.68038
[7] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman New York · Zbl 0411.68039
[8] Gurevich, Y., Complete and incomplete randomized NP problems, (Proc. 28th Annual Symp. on Found. of Computer Science, IEEE (1987)), 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: 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.”; 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.; 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, (Proc. 20th Symp. on Theory of Computing, ACM (1988))
[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.; 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. 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.