Intractability: a geometric representation

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

• ACM68: William F. Atchison , Samuel D. Conte , John W. Hamblen , Thomas E. Hull , Thomas A. Keenan , William B. Kehl , Edward J. McCluskey , Silvio O. Navarro , Werner C. Rheinboldt , Earl J. Schweppe , William Viavant , David M. Young, Jr., Curriculum 68: Recommendations for academic programs in computer science: a report of the ACM curriculum committee on computer science, Communications of the ACM, v.11 n.3, p.151-197, March 1968 [doi>10.1145/362929.362976]
• ACM79: Richard H. Austing , Bruce H. Barnes , Della T. Bonnette , Gerald L. Engel , Gordon Stokes, Curriculum '78: recommendations for the undergraduate program in computer science— a report of the ACM curriculum committee on computer science, Communications of the ACM, v.22 n.3, p.147-166, March 1979 [doi>10.1145/359080.359083]
• GT86: Norman E. Gibbs , Allen B. Tucker, A model curriculum for a liberal arts degree in computer science, Communications of the ACM, v.29 n.3, p.202-210, March 1986 [doi>10.1145/5666.5667]
• Kar72: 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.
• MT90: Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
• PS82: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• Sti87: D.R. Stinson. An Introduction to the Design and Analysis of Algorithms. The Charles Babbage Research Center, Winnipeg, Manitoba, Canada, 2nd edition, 1987.
• Tur91: A.J. Turner. Introduction to the joint curriculum task force report. Communications of the ACM, 34(6):69-79,1991.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Sequencing and scheduling

  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Computer science education

General Terms:
Algorithms, Performance