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 ${\cal A}$ is an algorithm that runs in time ${T(n)}$ in worst case, define the ${\delta}$truncated version to be the following algorithm: Let ${x}$ be an input of length ${n}$.

1. Run ${\cal A}$ on input ${x}$ for at most ${\delta T(n)}$ steps.
2. If during this time the algorithm accepts, then accept; if it rejects, then reject.
3. If it does not accept or reject in ${\delta T(n)}$ steps, then reject.

Definition Suppose that ${\cal A}$ is an algorithm for some decision problem that runs in worst case time ${T(n)}$. Say it is ${(\epsilon, \delta)}$progressive provided for at least ${\epsilon 2^{n}}$ inputs of length ${n}$, the ${\delta}$-truncated algorithm ${\cal A'}$ is correct.

Note, initially we think of ${\epsilon}$ and ${\delta}$ as constants, but they could also be functions of ${n}$.

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 ${2^{n}}$ 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 ${n}$ encodes a legal 3-CNF formula. A better way seems to be to adjust the definition so that a subset of all ${n}$ bit strings are identified as legal. Call this set ${L_{n} \subseteq \{0,1\}^{n}}$. Then the definition becomes:

Definition Suppose that ${\cal A}$ is an algorithm for some decision problem that runs in worst case time ${T(n)}$ with legal inputs ${L_{n}}$. Say it is ${(\epsilon, \delta)}$progressive provided for at least ${\epsilon |L_{n}|}$ inputs of length ${n}$, the ${\delta}$-truncated algorithm ${\cal A'}$ is correct.

## Explanation Of Wrong Lower Bound “Proofs”

I claim that many who have tried to prove that ${\mathsf{P}\neq\mathsf{NP}}$ 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 ${3}$${\mathsf{SAT}}$. This is the algorithm ${\cal B}$ that given a formula just tries all the assignments in order

$\displaystyle 0,1,2,\dots,2^{n}-1$

until one is correct: we identify strings of length ${n}$ with the corresponding number in the usual manner. Call a stage of ${\cal B}$ 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 ${\cal B}$ 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 ${\cal B}$ is progressive was wrong.

Here is what I tried. Consider the set ${L_{n}}$ of 3-CNF formulas on ${n}$ variables with ${cn}$ clauses for some constant ${c>0}$.

I needed to prove that if we stop the algorithm ${\cal B}$ at stage ${\delta 2^{n}}$, 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 ${L_{n}}$ 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 ${F}$ has equivalent formulas obtained by flipping one or more of its variables consistently through all its clauses. Thus

$\displaystyle \mathbf{x} \vee y \vee z, \mathsf{x} \vee z \vee w, \dots$

is equivalent to

$\displaystyle \mathbf{\bar{x}} \vee y \vee z, \mathbf{\bar{x}} \vee z \vee w, \dots$

Let ${[F]}$ be the equivalence class of ${F}$. It seemed clear that each formula has exactly ${2^{n}}$ equivalent formulas, including itself.

Wrong. This is not correct as Arefin pointed out. Consider the formula ${F}$:

$\displaystyle x \vee y, \bar{x} \vee \bar{y}.$

Here are ${4}$ flips of the variables in ${F}$:

$\displaystyle \begin{array}{rcl} x \vee y, && \bar{x} \vee \bar{y} \\ \bar{x} \vee y, && x \vee \bar{y} \\ x \vee \bar{y}, && \bar{x} \vee y \\ \bar{x} \vee \bar{y}, && x \vee y. \end{array}$

The first and the last are the same, and the second and the third are the same, so there are only two formulas in ${[F]}$ not four. This destroyed my argument and I am still thinking about how to proceed.

## Open Problems

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?

1. November 18, 2012 3:03 am

What I find interesting is that when there is a post of concrete topic/attack there are very few comments, whereas when there is general topic there are a lot of comments. Is it related to very specialized topics covered, that there are no qualified opinions around, or the general approach of mathematical community. As to progressive algorithms, they does not have to be consequitive bits, but also may be progressively increasing linear spaces. As an example, Nullstelenzats certificate can be represented as a matrix multiplied by the vector of monomials. In order for the matrix to be certificate, it has to be a full rank. So increasing the degree of certificate one reduces the nullspace of the matrix. When nullspace is not any more can be reduced there is high chance we have discovered Groebner basis. Moreover, one can perform search of Nulstellenzats certificate iteratively. Find the nullspace for degree 2, which gives less than squared number of indeterminates, then increase the degree, and workout the nullspace in terms of quadratic monomials if the indeterminates discovered in the previous step, etc. until stable basis or full rank matrix is discovered. That does not give polynomial time certificate discovery, but can be subexponential for NP complete problems.

November 18, 2012 12:12 pm

mkatkov,

Thanks for this comment. Ken and I worked very hard to get Ryan’s proof into the form we presented. We believe it is clearer and will probably make it into a full paper/survey. But it is interesting that it got zero comments.
dick

November 24, 2012 12:38 pm

It’s always true that technical posts (and blogs) get fewer comments than non-technical. I believe it’s simply because making comments of a technical nature is a lot more work. Everyone is ready to give their opinion on what is good notation, what is wrong with the academic community, how they think P v NP will be resolved, etc., but putting together a thoughtful technical post takes serious effort that not many casual readers will invest.

That said, I tend to enjoy the technical posts the most! I like being introduced to new concepts in TCS and I think the presentation here is very good.

• November 25, 2012 5:57 am

A little bit more details on http://mkatkov.wordpress.com/2012/11/25/np-complete-problems-and-tautologies/ I did not see this kinds of approache, but would be very interested if someone can point out references, or even keywords for search. The link above is one page summary, without details.

November 18, 2012 11:33 am

Just an observation: you can show nonconstructively the existence of a progressive brute force search algorithm for SAT. Let $A_w$ denote the brute force algorithm that tries satisfying assignments in the order $w, w+1, \ldots, 2^n-1, 0, \ldots, w-1$ (mod $2^n$). Consider the experiment in which $w$ is chosen uniformly at random. Then for each formula $\phi$, the probability that the $\delta$-truncated $A_w$ agrees with full $A_w$ on $\phi$ is at least $\delta$ (if $\phi$ is unsatisfiable, then they agree, otherwise, $\phi$ has at least one satisfying assignment, call it $w_0$, and $A_w$ finds it if $w$ was chosen from the range $\{ w_0 - \delta 2^n, \ldots, w_0\}$ mod $2^n$).

It follows that the expected agreement between $A_w$ and its $\delta$-truncated version is at least $\delta$. So there must exist some fixed $w$ which achieves at least as much agreement as the expectation.

For each input length, this gives you some progressive brute force search algorithm. But it doesn’t give you a *uniform* algorithm that is progressive for all input lengths.

November 18, 2012 12:06 pm

Mikero,

I fixed your comment so will show correctly. Thanks for great comment.

dick

PS Secret is dollar … dollar needs to be dollar latex … dollar

3. November 18, 2012 12:50 pm

Are you aware of the work on “anytime algorithms” (see here)? It is a related idea, but related more to quality of approximation than to decision problems.

November 18, 2012 11:19 pm

Your notion of progressive algorithms seems very much like average-case analysis. A problem is in Average-P in the Levin sense if there is an algorithm and polynomial p
so that the algorithm takes time more than p(n/\epsilon) only with probability epsilon.

The problem with average case analysis is to identify distributions on which analysis
is meaningful as a guide for observed performance on real inputs. The uniform distribution is rarely a good test set for NP-complete problems.

Russell Impagliazzo

5. November 19, 2012 2:43 am

Here is a proof that the brute force algorithm is $(\delta,\delta)$-progressive. It uses your variable-flipping idea in the second part.

Outline:
Step 1: Show that the algorithm is progressive for trivial formulae.
Step 2: Show that if the algorithm is progressive for trivial formulae, it must be progressive in general.

Proof:
Step 1: Let $m$ be the number of variables. Let’s say the brute force algorithm tries all the $2^m$ possible assignments in order. My idea is to consider the trivial 3CNF formulae, such as $x_1 \wedge \bar x_2 \wedge \cdots \wedge x_m$, i.e. formulae that have one solution, trivially. By trying the first $\delta 2^m$ possible assignments, we are guaranteed to correctly decide $\delta 2^m$ trivial formulae. This shows that the algorithm is progressive when applied to trivial formulae.

Step 2: Any satisfiable 3CNF formula must be implied by at least one trivial formula. That is, given any satisfiable 3CNF formula $\phi$, there exists at least one trivial formulae $\psi$ such that $\psi \Rightarrow \phi$. Now apply any of the $2^m$ possible variable-flippings on that implication to obtain $\psi’ \Rightarrow \phi’$. The variable-flippings might yield a smaller possible number of $\phi’$ formulae, but will still yield $2^m$ different $\psi’$ trivial formulae, which will be divided evenly among the available $\phi’$ formulae. This implies that the algorithm will find a satisfying assignment for $\delta L_m$ formulae in $\delta T(n)$ time.

The assertion that the $psi’$ formulae are divided evenly among the $\phi’$ formulae equivalence classes is crucial. This should be checked formally.

This proof can be reformulated without reference to trivial formulae — they are trivially isomorphic to certain variable assignments — but I think it helps to visualize the variable flipping happening to the entire implication.