Random instances of a graph coloring problem are hard

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Random instances of a graph coloring problem are hard

Full text

Pdf (544 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twentieth annual ACM symposium on Theory of computing table of contents

Chicago, Illinois, United States

Pages: 217 - 222

Year of Publication: 1988

ISBN:0-89791-264-0

Authors

Ramarathnam Venkatesan	Department of Computer Science, Boston University, 111 Cummington St, Boston, MA
Leonid Levin	Department of Computer Science, Boston University, 111 Cummington St, Boston, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 43, Citation Count: 12

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/62212.62231 What is a DOI?

ABSTRACT

NP-complete problems should be hard on some (may be extremely rare) instances. But on generic instances many such problems (especially related to random graphs) have been proven easy. We show the intractability of random instances of a graph coloring problem by modifying the NP-completeness theorem.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L. Babai, P. Erdos, M. Selkow, Random Graph Isomorphism, $1AM Journal of Computing 9 (1980) 628-635.
	2	R. Berger, The undecidability of the domino problem, Mere. A met. Math. Soc. 66, (1966).
	3	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	4	B. Bollob~s, Random Graphs, Academic Press (~98s).
	5	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	6	Yu. G urevich, Complete and incomplete Randomized NP Problems ~8th Annual Sympo- Mum on Foundations o/ Computer Science (1987), 111-117.
	7	Yuri Gurevich , Saharon Shelah, Expected computation time for Hamiltonian path problem, SIAM Journal on Computing, v.16 n.3, p.486-502, June 1987 [doi>10.1137/0216034]
	8	N. Ikeno, A 6-symbol 10-state Universal Turing Machine, Proceedings, Institute of Electrical Communications, (1958) Tokyo.
	9	D. Johnson, The NP-completeness column-an ongoing guide, Journal of Algorithm.s 5 (1984), 284-299.
	10	J.C Lagarias, A.M. Odlyzko, Solving Low density subset sum problems, in Proc. 24th Ann. Syrup. on Foundations of Computer Science, (1983), pp 1-10.
	11	Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
	12	R. Robinson, Undecidability and non-periodicity for tiling a p}ane, lnvencione Mathematicae 12 (1971) 177-209.
	13	A. Shamir, A polynomial algorithm for breaking the basic Markle-Hellman Cryptosystem, IEEE Symposium on Foundations of Computer Science (1982), 145-152.
	14	A.C. Yao, Theory and Applications of Trapdoor Functions, IEEE Syrup. on Foundations of. Computer Science (1982) 80-91.

CITED BY 12

	Ari Juels , Marcus Peinado, Hiding cliques for cryptographic security, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.678-684, January 25-27, 1998, San Francisco, California, United States
	S. Ben-David , B. Chor , O. Goldreich, On the theory of average case complexity, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.204-216, May 14-17, 1989, Seattle, Washington, United States
	Richard J. Lipton , Neal E. Young, Simple strategies for large zero-sum games with applications to complexity theory, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.734-740, May 23-25, 1994, Montreal, Quebec, Canada
	Ramarathnam Venkatesan , Sivaramakrishnan Rajagopalan, Average case intractability of matrix and diophantine problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.632-642, May 04-06, 1992, Victoria, British Columbia, Canada
	Jie Wang, Average-case completeness of a word problem for groups, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.325-334, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Ari Juels , Marcus Peinado, Hiding Cliques for Cryptographic Security, Designs, Codes and Cryptography, v.20 n.3, p.269-280, July 2000
	Jie Wang, Complete on average Boolean satisfiability, Journal of Complexity, v.18 n.4, p.1024-1036, December 2002
	Dan Gutfreund , Ronen Shaltiel , Amnon Ta-Shma, If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances, Computational Complexity, v.16 n.4, p.412-441, December 2007
	Candelaria Hernández Goya , Pino Caballero Gil, Using average case intractability in cryptography, Proceedings of the 4th WSEAS International Conference on Applied Informatics and Communications, p.1-5, December 17-19, 2004, Tenerife, Canary Islands, Spain
	Jue Xue, Solving the Minimum Weighted Integer Coloring Problem, Computational Optimization and Applications, v.11 n.1, p.53-64, Oct. 1998
	Leonid A. Levin, Fundamentals of computing (a cheatlist), ACM SIGACT News, v.27 n.3, p.89, Sept. 1996
	Oliver Riordan, Spanning Subgraphs of Random Graphs, Combinatorics, Probability and Computing, v.9 n.2, p.125-148, March 2000