Progress On Progressive Algorithms
Another attempt to capture the notion of progressive and a wrong proof of mine
Gary Miller is one of the great theorists. Starting with his award winning PhD thesis on a connection of the Riemann Hypothesis with primality testing, to his later work on graph separators, to his more recent work on practical methods for solving special linear systems in almost linear time, he has always done world class research.
Today I want revisit a idea that Ken and I have talked about before—the notion we called progressive algorithms.
We ended that previous discussion with a question.
A final question is: can we prove that many actual algorithms are progressive? I would conjecture that many “real” algorithms are progressive—either in the exact sense defined here, or in some small variation.
Back to Gary. He is a long-time friend of mine, who once said to me—I wish I could recall the exact phrase—the following:
If you have the right definitions, then the proof should be easy.
I am not sure I completely believe this, but there is much truth in his statement. I do think that Ken and I are closer to the right definition of progressive than before, and we can hope that Gary’s dictum will allow us to finally make some progress—bad pun—on progressive algorithms.
Progressive Algorithms—Take Two
The reasoning behind Gary’s statement is that with the right definition you can think clearly about the issues and see what should be true, what can be proved, and what may be proved in the future. In our previous attempt to understand the notion of progressive our definition was not crisp enough to allow any serious research to start. But we now have a definition that feels “right.” Of course we will see if our intuition is on target—the ultimate test is proving some interesting results.
If is an algorithm that runs in time in worst case, define the -truncated version to be the following algorithm: Let be an input of length .
- Run on input for at most steps.
- If during this time the algorithm accepts, then accept; if it rejects, then reject.
- If it does not accept or reject in steps, then reject.
Definition Suppose that is an algorithm for some decision problem that runs in worst case time . Say it is -progressive provided for at least inputs of length , the -truncated algorithm is correct.
Note, initially we think of and as constants, but they could also be functions of .
A further comment on the definition. We are interested mainly in what might be called existential progressive (whose truncated version rejects by default) and not universal progressive (which searches for a counterexample and whose truncated version therefore accepts by default). In this initial discussion we will leave the definition as is, but this may be a useful distinction in the future.
A Problem With The Definition
I claim that this definition captures the intuitive notion that the algorithm is actually searching through the solution space for a solution. It is making progress as it runs.
But there is a problem with the definition, which is related to the encoding of inputs. Consider an algorithm that takes as inputs 3-CNF formulas and does brute-force search for a potential satisfying assignment. Intuitively this algorithm should be progressive—no? As it runs through the possible assignments in a fixed order, one would expect that it would satisfy our definition.
There is a difficulty, however. The issue is of the inputs many of them are not legal encodings of a 3-CNF formula. This means that the algorithm may fail to be progressive or may be progressive for a trivial reason. Note the algorithm that just says “NO” is likely to be right, since most inputs do not encode a 3-CNF correctly.
There are several ways to fix this. We could use a non-standard encoding so that every string of length encodes a legal 3-CNF formula. A better way seems to be to adjust the definition so that a subset of all bit strings are identified as legal. Call this set . Then the definition becomes:
Definition Suppose that is an algorithm for some decision problem that runs in worst case time with legal inputs . Say it is -progressive provided for at least inputs of length , the -truncated algorithm is correct.
Explanation Of Wrong Lower Bound “Proofs”
I claim that many who have tried to prove that have really been trying to show that any progressive algorithm cannot work.
Let me elaborate on what I mean by this. Their arguments often go something like this: any algorithm that solves—pick your favorite hard search problem—must look at all the cases. But this requires an exponential amount of time. QED. This is of course wrong, but perhaps could be proved for progressive algorithms?
An Example Of A Progressive Algorithm?
Right after creating this new definition I thought that I would prove that some simple search algorithm is progressive. A good idea in research is to start with the simplest case possible, then try more and more complex cases. So I selected the brute-force search algorithm for -. This is the algorithm that given a formula just tries all the assignments in order
until one is correct: we identify strings of length with the corresponding number in the usual manner. Call a stage of the testing of an assignment on the 3-CNF formula to see i it is satisfied. Then I claim that this algorithm is progressive in our new sense.
This seemed like a pretty straightforward claim. So I sat down and started to type in the proof. My idea was that if had tried say half the assignments, then “obviously” it would have handled correctly half the 3-CNF formulas. My intuition was—and still is—that this seemed reasonable. Why would a satisfiable formula be biased on which assignment worked?
Enter Arefin Huq, who is a graduate student at Tech and is currently helping me with my complexity class. We discussed this notion of progressive a number of times and he pointed out that my initial attempt at a proof that is progressive was wrong.
Here is what I tried. Consider the set of 3-CNF formulas on variables with clauses for some constant .
I needed to prove that if we stop the algorithm at stage , then a positive fraction of the legal strings are correctly handled. This sounds trivial, perhaps it is, but I cannot see a trivial proof. The point is that we must argue that of the legal inputs they are equally likely to be satisfy by an early assignment as a later one.
My attempt was based on a very simple notion: that of flipping variables. Every formula has equivalent formulas obtained by flipping one or more of its variables consistently through all its clauses. Thus
is equivalent to
Let be the equivalence class of . It seemed clear that each formula has exactly equivalent formulas, including itself.
Wrong. This is not correct as Arefin pointed out. Consider the formula :
Here are flips of the variables in :
The first and the last are the same, and the second and the third are the same, so there are only two formulas in not four. This destroyed my argument and I am still thinking about how to proceed.
Can you prove that the brute force search algorithm for 3-CNF is progressive? It seems like it should be true, but also seems like it is not so easy. Perhaps Gary’s dictum suggests that we still do not have the right definition. What do you think?