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.

__ Definition.__
Say that an algorithm

there is a positive integer *k* so that,

*A* runs in time O(*n*^{k}),

where *n* is the length of *x*.

For example, an algorithm that takes no more than *n*^{3} 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.