Example: Suppose that I have an array of n non-negative integers, all less than d. How many bits would be required to represent this array? Well, you'd have to write down n and d and then you'd have to write down all n of the array elements. It takes roughly lg(x) bits to write down the number x, so this would require lg(n) + lg(d) + n*lg(d) = Θ(n lg(d)) bits. If you want to be picky, you'll have to be a bit clever to make sure that the person can interpret all the bits correctly. For example:What input does this represent: 11111011011101011000010100 ? could be: 111 11 011 011 101 011 000 010 100 n=7 d=3 3 3 5 3 0 2 4 could be: 11 111 0110111 0101100 0010100 n=3 d=7 55 44 20Fortunately, we don't need to worry too much about this. With even a really silly plan, we could encode this without doing worse than, say, quadrupling the number of bits used. Thus, we could still encode our problem in Θ(n lg(d)) bits.
Just this once, I want you to worry about precisely what I said you didn't need to worry about in the above example. I want you to describe a scheme with which you could encode an array of n non-negative integers, all of which are less than d, as a string of bits. From your description I should be able to easily figure out how to encode any such array, without any limits whatsoever on n and d ... even if n and d were *HUGE*. This scheme must be unambiguous, in other words there can't be two different possible interpretations, like what I did above. Turn In: a description of your encoding scheme, an example n, d and array encoded according to your scheme, and an analysis of how many bits your method requires as a function of n and d.
Other study problems (not to turn in)
.--------- terminates the unary field width
|
V
1 1 1 0 1 0 1 ← represents the number 5
----- -----
Tells 3-bit
me n representation
takes of the number 5.
3 bits
What is the list of numbers reprsented by:
1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 0 1 0
TA(n) = n^2 - 3*n + 1,
TB(n,k) = n^n + 1, n*k + k^2,
TC(n,k) = n*lg(k),
TD(n) = sqrt(n) + 2*n.
We've already seen this problem addressed in one case: sorting! In Class 14 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? 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 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. 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 |
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.