**P2**from Week 11 quiz questions (take home, to be done before Class 28)

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(S^{k}) 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(S^{k/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.