Understanding Complexity Classes of Problems
Nearly all of the algorithms introduced so far run in polynomial time (for instance, on inputs of size n, their worst-case running time is O(nk) for constant k). However, there are problems that simply cannot be solved or for which a polynomial-time algorithm hasn't been found yet.
An example of a problem that cannot be solved is the halting problem. The halting problem is the problem of determining, from the description of a computer program and an input, whether the program will finish running or continue to run forever. Alan Turing proved that a general algorithm to solve the halting problem for all pairs of (program, input) cannot exist.
It is common to call problems solvable by polynomial-time algorithms (for instance, those whose worst-case running time is O(nk) for constant k) as "tractable", or "easy", and problems that require a super-polynomial-time algorithm (for instance, those whose running time is not bounded above by any polynomial...
