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 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.