Cited By
View all- Mehta DRosenthal JScharlau BMcDermott RPears ASabin M(2019)AlgoBOWLProceedings of the 2019 ACM Conference on Innovation and Technology in Computer Science Education10.1145/3304221.3319761(471-477)Online publication date: 2-Jul-2019
Intractability: a geometric representation
Author: 
Sami KhuriAuthors Info & Claims
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, ...
Intractability of Clique-Width Parameterizations
We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are $W[1]$-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when ...
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]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 March 1994
Published in SIGCSE Volume 26, Issue 1
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 240Total Downloads
- Downloads (Last 12 months)37
- Downloads (Last 6 weeks)12
Reflects downloads up to 27 Nov 2024
Other Metrics
Citations
Cited By
View all- Mehta DRosenthal JScharlau BMcDermott RPears ASabin M(2019)AlgoBOWLProceedings of the 2019 ACM Conference on Innovation and Technology in Computer Science Education10.1145/3304221.3319761(471-477)Online publication date: 2-Jul-2019
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