Abstract
This paper introduces a geometric representation that can be applied to illustrate the complexity of some combinatorial optimization problems. In this work, it is applied to the 0/1 knapsack problem and to a special case of a scheduling problem. This representation gives insight into the difference between tractable and intractable problems. It can therefore be used as a stepping stone to compare polynomial (P) and nondeterministic polynomial (NP) problems, before venturing into the world of NP-completeness.
References
[1]
ACM Curriculum Committee on Computer Science. Curriculum 68: Recommendations for academic programs in computer science. Communications of the ACM, I 1 (3): 151-197, 1968.
[2]
ACM Curriculum Committee on Computer Science. Curriculum 78: Recommendations for the undergraduate program in computer science. Communications of the ACM, 22(3):147-166, 1979.
[3]
N. Gibbs and A. Tucker. A model corriculum for a liberal arts degree in computer science. Communications of the ACM, 29(3):202-210, 1986.
[4]
R.M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computation, pages 85-103. Plenum, New York, 1972.
[5]
S. Martello and P. Toth. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Chichester, West Sussex, England, 1990.
[6]
C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1982.
[7]
D.R. Stinson. An Introduction to the Design and Analysis of Algorithms. The Charles Babbage Research Center, Winnipeg, Manitoba, Canada, 2nd edition, 1987.
[8]
A.J. Turner. Introduction to the joint curriculum task force report. Communications of the ACM, 34(6):69-79,1991.
Index Terms
- Intractability: a geometric representation
Recommendations
Average-case intractability vs. worst-case intractability
We show that not all sets in NP (or other levels of the polynomial-time hierarchy) have efficient average-case algorithms unless the Arthur-Merlin classes MA and AM can be derandomized to NP and various subclasses of P/poly collapse to P. Furthermore, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1994 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 March 1994
Check for updates
Qualifiers
- Article
Conference
SIGCSE94
Sponsor:
SIGCSE94: 25th SIGCSE Technical Symposium on Computer Science Education
March 10 - 12, 1994
Arizona, Phoenix, USA
Acceptance Rates
Overall Acceptance Rate 1,595 of 4,542 submissions, 35%
Upcoming Conference
SIGCSE TS 2025
- Sponsor:
- sigcse
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 241Total Downloads
- Downloads (Last 12 months)34
- Downloads (Last 6 weeks)4
Reflects downloads up to 12 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in