Most of the algorithms we looked at so far are in the first category. The Towers of Hanoi algorithm is an example of the second category. 20.1 The Classes P and NP A problem is said to be tractable if it can be solved by an algorithm which has worst-case polynomial complexity.
Most optimization problems have an equivalent decision problem version.
The set of all decision problems for which a polynomially bounded algorithm exists. Run a verification algorithm to determine whether the guess S is correct. No one really thinks so, but no one has been able to prove or disprove. Construct the complete graph K n . These are the hardest of the problems for which no polynomially bounded algorithm has been found .