Intractability

摘要

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.