9.2. Polynomial Time

With this chapter, we turn to complexity theory, which is concerned with efficient computability.

The first issue is, how should efficiency be defined?

There are a lot of possible answers. For now, we will settle on a simple definition: efficiency means polynomial time.

Polynomial time

Definition. Say that an algorithm A runs in polynomial time if

there is a positive integer k so that,
  A runs in time O(nk),

where n is the length of x.

For example, an algorithm that takes no more than n3 steps runs in polynomial time, or is a polynomial time algorithm.

If we accept, for the moment, that a polynomial time algorithm is "efficient", then it makes sense to give a name to decision problems that have efficient algorithms.

Definition. P is the class of all decision problems (languages) that can be solved by polynomial time algorithms.

Notice that the definition has nothing to do whether you or I are clever enough to find a polynomial time algorithm for the problem. A decision problem is in P if there exists a polynomial time algorithm for it.