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): 16, Downloads (12 Months): 79, Citation Count: 7

Additional Information:

abstract cited by index terms review 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/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

	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
	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
	Vladmir Estivill-Castro , Derick Wood, A survey of adaptive sorting algorithms, ACM Computing Surveys (CSUR), v.24 n.4, p.441-476, Dec. 1992
	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
	Leonid A. Levin, Fundamentals of computing (a cheatlist), ACM SIGACT News, v.27 n.3, p.89, Sept. 1996

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

Adobe Acrobat

QuickTime

Windows Media Player

Real Player