The Complete Codes

  NP-Completeness Most of the problems considered up to now can be solved by algorithms in worst-case polynomial time. There are many problems and it is not necessary that all the problems have an apparent solution. This concept, somehow, can be applied to solving the problem using computers. The computer can solve: some problems in a limited time e.g. sorting, some problems require an unmanageable amount of time e.g. Hamiltonian cycles, and some problems cannot be solved e.g. I-lasting Problem. In this section, we concentrate on the specific class of problems called NP-complete problems (will be defined later). Tractable and Intractable Problems We call problems as tractable or easy if the problem can be solved using polynomial-time algorithms. The problems that cannot be solved in polynomial time but require a super polynomial-time algorithm are called intractable or hard problems. There are many problems for which no algorithm with running time better than exponential time is kn