P, NP and Exponential Type Problems

Page last updated 04/19/99

Complexity of an Algorithm

In computer science algorithms are classified together by counting the number of steps it takes to process a data set of n items. The data set can be the number records in a database, the number of characters in a document, the number of bits in a password, the number of numbers on which a statistic is to be computed, etc.

The equation that represents the number of steps that the algorithm takes is usually expressed in terms of n, the size of the data set. Since we are interested in the ability of the algorithm to process large quantities of data, computer scientists concern themselves with the case when n gets very large. In this case it is sufficient to concern ourselves with the term of the equation that is of the largest power. All other terms and constants in the equation can be ignored.

Asymptotic growth of numbers

This chart represents how long a computer that can execute 1 million steps per second would take to process n data items if the algorithm was classified as the function at the top of the chart.

Value of n	n	n²	n³	n⁴	2ⁿ	3ⁿ	n!	nⁿ
1	0.000001 sec.	0.000001 sec.	0.000001 sec.	0.000001 sec.	0.000001 sec.	0.000001 sec.	0.000001 sec.	0.000001 sec.
5	0.000005 sec	0.000025 sec	0.000125 sec	0.000625 sec	0.00032 sec	0.000243 sec	0.00012 sec	0.003125 sec
10	0.00001 sec	0.0001 sec	0.001 sec	0.01 sec	0.001024 sec	0.059049 sec	3.63 sec	2.78 hrs
20	0.00002 sec	0.0004 sec	0.008 sec	0.16 sec	1.058 sec	58.1 sec	78218 yrs	3.37x10¹² yrs
50	0.00005 sec	0.0025 sec	0.00125 sec	0.625 sec	26.2 yrs	2.3x10¹⁰ yrs	9.77x10⁶⁰ yrs	2.87x10⁷⁰ yrs
75	0.000075 sec	0.005625 sec	0.422 sec	31.6 sec	1.21x10⁹ yrs	1.95x10²² yrs	1.95x10⁹⁷ yrs	1.35x10¹²⁷ yrs
100	0.0001 sec	0.01 sec	1.00 sec	1.667 min	4.0x10¹⁷ yrs	1.63x10³⁴ yrs	3.0x10¹⁴⁶ yrs	3.2x10¹⁸⁶ yrs
200	0.0002 sec	0.04 sec	8.00 sec	44.44 hrs

Notice the significant change in solution time between the red and blue, especially when n a large, but reasonable value of 50 or more.

Example problem and 2 algorithms to solve the problem.

Consider the task of sorting a deck of cards (n = 52).

Solution 1:

Search through the deck to find the smallest valued card.
Lay that card aside
Search through the deck for the next smallest valued card.
Lay that card on top of the smaller card.
Repeat steps 3 and 4 for each of the remaining cards.

Solution 2:

Methodically permute the deck in a way that all permutations may be visited
Check the deck after each permutation to see if the deck is in sorted order.

The first solution searches through n cards (albeit n decreases each time) and we do the process n times. The number of steps then is on the order of n².

The second solution requires generating each of the permutations. There are n! (factorial) permutations. That alone makes the running time significant. Check the second most right column of the table.

Different classes of problems

Class P problems

Any problem that has a running time on the order of a polynomial number of steps is considered P type problem. That is, the best algorithm that can be found runs in polynomial time. Sample running times for class P problems are indicated in blue in the above table.

Exponential problems

Any problem that has at best a running time in exponential time (those in red) are called exponential algorithms. Are there such problems? Yes. An example is an algorithm that cracks passwords. You must try all combinations of letters in order to guess the password and that becomes an exponential algorithm.

Unsolvable problems

We saw earlier that there are problems that are unsolvable, such as the Halting Problem

Intractable problems

Any problem that is unsolvable or can only be solved in exponential time is called "intractable".

Class NP problems

Are there problems that appear to be intractable (exponential solutions exist)
but we don't know that they are not intractable?

Take the second solution of the sorting problem. If we had many computers tied into a network. We can distribute the work among the computers in the following way. Each computer can be given the original data set and be programmed to perform a unique permutation. If a computer finds its permutation generates the sorted sequence then it needs to report that back to a main controlling computer.

In this case the number of steps becomes polynomial, if we have enough computers to share in the workload. An algorithm that can be done in polynomial time with enough machines, but requires exponential time with a single machine is considered NP.

Class NP problems may be P problems. We don't know. It seems that a solution to NP problems would be found by now. For the time being we don't think that P = NP, but we don't have a proof of it.

The Traveling Salesman Problem (TSP).

A salesman must visit a number of cities. He does not want to visit the cities more than once and needs to keep the cost to a minimum. Given the cost of traveling between two adjacent cities, what is the best route for the salesman to take that minimizes the cost.

A solution is to generate an exhaustive list and search the list for the best solution. In this case there is no analogous class P solution like there was for sorting.

There are a whole class of problems similar to TSP. Each of the problems that can be efficiently transformed (in polynomial time) to an equivalent TSP are considered to be NP also. "Satisfiability" and "bin-packing" are examples of problems that can be transformed to TSP. Actually the Satisfiability problem is the typical target problem for testing if a problem is in NP.

If a solution is ever found to any of the NP problems, we will have found solutions to all the problems in that classification.