We've already seen this problem addressed in one case: sorting! In an earlier class we proved that any general purpose sorting algorithm, including those that have yet to be invented, has a worst case time complexity that is Ω(n lg n), where n is the number of elements to be sorted. (Remember that mergesort actually meets this bound.) Thus, sorting is inherently n log n ... you can't do better in the worst case.
Why now? Why are we looking at these questions at this point in the semester? Well, for one reason, we've looked at a public key cryptography system based on integer factorization. In this systems, and in other public key systems, security rests on the presumed difficulty of some computational problem. It's not that our current algorithms are slow, it's that we expect that the problem is inherently difficult - i.e. that any algorithm solving it would be slow. Thus, these crypto-systems naturally move us to ask questions about the inherent difficulties of problems.
To make this precise, we'll consider the problem power(3,n), i.e. computing powers of 3. Since our divide and conquer algorithm solves this problem in Θ(lg n) time, we're tempted to say that this must be an easier problem than max. However, I've tricked you a bit. What relationship is there between the "n" from the max problem and the "n" from the power(3,n) problem? None! For each problem, we choose a different parameter to use as our "input size", and we analyze the complexities of our algorithms in terms of these parameters. For different algorithms solving the same problem, this is fine (as long as we analyze our algorithms in terms of the same parameters), but if we're going to compare different problems, we need a universal standard that we can use to measure input size, and we need to analyze problems/algorithms complexities in terms of this universal standard. We'll use "bit size" to do this. In other words, the size of a particular instance of a problem is the number of bits required to write down that problem instance.
Inportant fact: It take 1 + ⌊ lg k ⌋ bits to represent a positive integer k.
So, returning to the problem of power(3,n), we have a Θ(lg n) algorithm using divide and conquer, but what is the complexity of this algorithm in terms of the bit size of the input? Well, the input is the number n, and it takes lg(n) bits (approximately) to represent n. So our bit size S = lg n. Therefore, our Θ(lg n) algorithm is a Θ(S) algorithm, i.e. it's linear in the bit size. Of course, no exponentiation algorithm can be sub-linear in the input size, since it has to read the entire number n in order to determine the answer. So, power(3,n) is linear in the bit-size of its input, just like max, so the two problems are of the same difficulty.
Note: this assumes that all comparisons and arithmetical operations take constant time - an assumption that, if we are doing integer exponentiation, is certainly not true! To be more precise, we need to pin down our problems precisely enough to factor these costs in as well.
|x^3 - 2||polynomial|
|x^3 - lg(x - 3)||not a polynomial, "lg" is not one of the approved operations|
|-2*(x - 3)^2 + 4*x*(x^3 - 1)||polynomial|
|(3*x^2 - 2)^k, where k = 7||polynomial|
|2^x - 1||not a polynomial, only constant exponents are allowed|
Important! An algorithm is "polynomial time" if it is O(p(n)) for some polynomial p. Thus, even though binary search is Θ(lg n) and lg n is not a polynomial, it is polynomial time because it is also O(n).
This choice of definitions for tractable and intractable is philosophical, not mathematical. There is logic behind it however. An problem requiring time Θ(n^100) would certainly be unreasonably difficult to solve, but it just doesn't seem to arise in practice. The exponent is typically small if it exists. This definition has some other nice properties. For example, if an algorithm runs in polynomial time on your desktop computer, it also runs in polynomial time on a Turing machine ... of course the exponent my be quite a bit larger on the Turing machine! [Turing machines are a standard mathematical model of computation.]
Another nice feature of our definition of intractibility, is that it allows us to be somewhat sloppy about measuring input size. For example: Suppose we have an algorithm that we've analyzed as running in time O(Sk) and ... oops, the actual input size is the really the square of S! So, the acutal input size, call it T, is T = S^2. So the algorithm runs in time O((√T)k) = O(Sk/2), which is still polynomial. So if the actual bitsize of the input is a polynomial in what you've used as input size, polynomial time algorithms stay polynomial.
NP is the class of problems for which solutions can be verified in polynomial time. For example, we don't know of any polynomial time solution for the 0/1 Knapsack Problem. However, we certainly know how to verify that a purported solution is in fact a solution in polynomial time - just add up the weights in the purported solution and see if the result equals the capacity. Actually, there's another requirement too, namely that the bit-length of any purported solution is polynomial in the bit size of the problem (or equivalently that the number of possible solutions is exponential in the bit length of the problem).
If we can solve a problem in polynomial time, we can certainly verify a solution in polynomial time, so any problem in P is certainly in NP. But is this true the other way 'round? Or are there problems in NP that are not in P? Most everybody believes that there are, but nobody knows.
Therefore, if a problem is in NP then we know that it can be solved in exponential time. The big question is whether it can be solved faster ... perhaps in polynomial time.