Fast Exponential Algorithms
An exponential algorithm for knapsack
Alan Perlis won the first Turing Award for his pioneering work on computer languages. He helped create the now famous department of computer science at Carnegie-Mellon University, then later in his career he created another department at Yale University. Alan was always smiling even through he spent much of his adult life in a wheel chair. He delighted in all things, especially anything about computing. You could walk in his office anytime and chat about just about anything. My connection with Alan was as a graduate student at Carnegie-Mellon, and later as a junior faculty at Yale when he was the chair there.
Perlis was famous for many “sayings”. He talked about “one man’s constant is another’s variable,” he coined the term “Turing Tar-pit”. The latter referred, of course, to the fact that just about anything interesting that one wanted to do with computers was undecidable. He talked about the “IBM fog descending over all”–recall this was when IBM was the dominate player in computers.
Polynomial vs. Exponential Algorithms
Alan had one saying that is quite relevant to P=NP: he once said, “for every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run”. His point is simple: if your algorithm runs in than an algorithm that runs in is faster for . While this is a simple point I think that it is a profound one. When we talk about P=NP we must not forget that the actually running time of the algorithm is the key. For example, if there is a factoring algorithm that runs in time such an algorithm would easily break all today’s factor based crypto-systems. Yet it’s asymptotic performance would pale when compared to the best known factoring methods.
An Exponential Algorithm for Knapsack
One of my favorite algorithms is one for the knapsack problem that runs in time exponential in , but the exponential term is instead of the obvious . This is a huge improvement over the obvious method. I have no idea who this algorithm is due to. I have known about it for decades–I would be greatly interested in any reference to it. But please to be the “first” the reference has to be before 1974, at least.
Recall the knapsack problem is the question of whether or not given the positive integers , there is a subset of the indices to
where is another given positive integer. The obvious algorithm would try all subsets . Since there are non-empty subsets the algorithm takes a long time.
The cool algorithm makes one small observation. The above equation can be re-written as follows:
where and . (Yes, we assume that is even, but if is odd the method can easily be fixed.) Then, the algorithm computes two sets. The first consists of all the values of
where ; and the second consists of all values of
where . We then simply check to see if these two have a value in common. The point is that they have a value in common if and only if the knapsack problem has a solution. The punch-line is that the cost for this is now dominated by the number of values in each set: . Note, checking if they have a common value can be done either by hashing or by sorting. But, in either case, this takes time just slightly larger than the sum size of the sets. Very neat, I think.
The above algorithm relies on the following idea. Suppose that and are finite sets of integers, and define . Then, determining whether or not is in can be done in time if hashing is used. (If you use sorting the time goes up by a log-term.) Note, this is potentially much faster than a brute force search of the set .
A natural problem is what happens with a set like ? Is there a way to tell if is in this set in time , for example? If this is possible, then the knapsack problem has an algorithm whose exponential term is . I have thought about this and related approaches quite often. I have yet to discover anything, I hope you have better luck.