Combinatorics, complexity, and randomness

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Combinatorics, complexity, and randomness

Full text

Pdf (1.13 MB)

Source

Communications of the ACM archive
Volume 29 , Issue 2 (February 1986) table of contents

Pages: 98 - 109

Year of Publication: 1986

ISSN:0001-0782

Author

Richard M. Karp

Univ. of California, Berkeley

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract cited by index terms review collaborative colleagues peer to peer

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/5657.5658 What is a DOI?

ABSTRACT

The 1985 Turing Award winner presents his perspective on the development of the field that has come to be called theoretical computer science.

CITED BY 7

	Guang-Ming Wu , Yao-Wen Chang, Quasi-Universal Switch Matrices for FPD Design, IEEE Transactions on Computers, v.48 n.10, p.1107-1122, October 1999
	J. Howard Johnson, Using textual redundancy to study The Mintainability of source, Advances in software engineering, Springer-Verlag New York, Inc., New York, NY, 2002
	Guang-Min Wu , Yao-Wen Chang, Switch-matrix architecture and routing for FPDs, Proceedings of the 1998 international symposium on Physical design, p.158-163, April 06-08, 1998, Monterey, California, United States
	Christopher Cherniak, Undebuggability and cognitive science, Communications of the ACM, v.31 n.4, p.402-412, April 1988
	Leonid A. Levin, Fundamentals of computing (a cheatlist), ACM SIGACT News, v.27 n.3, p.89, Sept. 1996
	Vladmir Estivill-Castro , Derick Wood, A survey of adaptive sorting algorithms, ACM Computing Surveys (CSUR), v.24 n.4, p.441-476, Dec. 1992
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994

INDEX TERMS

Classification:
F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.1.3 Complexity Measures and Classes
Subjects: Relations among complexity classes; Reducibility and completeness
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS

K. Computing Milieux
K.2 HISTORY OF COMPUTING
Subjects: People

General Terms:
Algorithms, Performance, Theory

REVIEW

"S. Srinivasan : Reviewer"

This is the ACM 1985 Turing Award Lecture paper. In this expository paper, the author traces the history of the work in the area of computational complexity. The chart on the development of combinatorial optimization and computational complexity more...

Collaborative Colleagues:

Richard M. Karp: colleagues

Peer to Peer - Readers of this Article have also read:

Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein
Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM 34, 12
Ellen Francik , Susan Ehrlich Rudman , Donna Cooper , Stephen Levine
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski

Adobe Acrobat

QuickTime

Windows Media Player

Real Player