As a brief review, we first discuss the different categories of functions for big-O notation:
The ones that involve n as an exponent (n! or nn) are called exponential functions. Functions whose growth is <= nc for some relatively small constant c are polynomial functions. Linear functions have growth proportional to n. Sub-linear functions have growth proportional to log n. A constant time function has growth independent of n
These descriptions of functions are frequently used to characterize different sets of problems. The general categories are:
Intractable or Exponential time problems: These are problems that require exponential time. Moreover, it has been proven that a solution in less than exponential time is impossible. For example, consider the problem of listing all possible committees of size one or more that could be formed from a group of n people. There are 2n - 1 such committees so any algorithm that solves this problem must have at least 2n - 1 steps, and thus a running time proportional to 2n. This problem cannot possibly have a polynomial solution.
Polynomial Time Problems: These are problems for which sub-linear, linear or polynomial solutions exist. Insertion sort, quicksort, mergesort and other sorting algorithms are good examples, as well as finding the smallest or largest values in a list. Any algorithm whose running time grows proportional to a polynomial function can solve reasonable-size problems if the constant in the exponent is small.
NP-Complete: No polynomial solution has been found, although exponential solutions exist. However, it has not been proven that a polynomial solution could not be found.
Some famous examples:
1) Traveling Salesperson (TSP): Given a map of cities and a cost of travel for each pair of cities, is it possible to visit each city exactly once and return home for less than k bucks?
2) n-bookshelf packing: You are given k books to put on n shelves. Will they fit? (the books are all of different sizes).
This group of problems is very interesting for a number of reasons. First of all, the "NP" means "nondeterministic polynomial". Nondeterministic does not mean that we have not yet been able to determine if the problem is polynomial. It means that the algorithm that we might define to solve one of these problems is non-deterministic, i.e., there is an element of chance in the algorithm. For example, we might write a solution as follows for the Traveling Salesperson problem:
Choose one of the possible paths, and compute its total cost. If this cost is no greater than the allowable cost, then declare a success else declare nothing.
Someone must choose one of the possible paths (this is the nondeterministic part). If we choose the right one, the problem is solved quickly; if not, we learn nothing. We define the running time of an NP algorithm as the time required to execute the algorithm if we make the "right" choice, meaning the choice that would lead to a solution in the optimal amount of time. So we are trying to measure how good the algorithm is, not how good our choices are.
According to this definition, the Traveling Salesperson problem has a polynomial solution. If we make the right choice, we just have to compute the distance for n cities which is proportional to n.
Of course, the class of NP problems includes the truly polynomial problems. If we can design a deterministic (no choices) polynomial solution for a problem, then we surely can design a nondeterministic one. In addition, the Traveling Salesperson problem suggests that there might be NP problems that do not have polynomial solutions. In other words, there appear to be problems that can be solved in polynomial time by nondeterministic algorithms, but that might require exponential time by a deterministic algorithm. But no one has been able to prove this. In particular, no one has been able to show that there does not exist a polynomial solution to the Traveling Salesperson problem. This is still one of the open questions in theoretical computer science (but most computer scientists are of the opinion that a polynomial solution does not exist for TSP).
Characteristics of NP-Complete Problems
In general the NP Complete Problems exhibit the following characteristics:
Each problem is solvable, and a relatively simple approach solves it (although the approach may be very time-consuming). For each of them, we can simply enumerate all the possibilities, all ways of assigning the logical values of n variables, all subsets of the set S. If there is a solution, it will appear in the enumeration; if not, we will discover this as well.
There are 2n cases to consider if we use the enumeration approach. Each possibility can be tested in a relatively small amount of time, so the time to test all possibilities and answer yes or no is proportional to 2n.
The problems are apparently unrelated coming from logic, number theory, graph theory, etc.
If it were possible to guess perfectly, we could solve each problem in a very small amount of time. The verification process could be done in polynomial time, given a good guess.
This concludes my first tutorial here at DIC, I hope you enjoy it and found it useful. I am looking to further expand it as and when I get the time. Make sure to post a comment as your feedback.