Designing Algorithms for Expected Performance

Yuri Gurevich

July 16, 1999

1. Reservations

This talk is a tribute to Eric's persuasion.

There were good reasons for me not to talk.

1a. I have moved to Volume B computer science.

1b. All my work on average case complexity was "negative"

with one exception:

Y. Gurevich and S. Shelah,

``Expected computation time for Hamiltonian Path Problem",

SIAM J. on Computing 16:3 (1987), 486--502.

Notice, however, the great practicality of negative results [GJ].

2. Search problems

A search problem is similar to a decision problem, but you are

required to produce a justification of your answer, a witness.

Consider for example SAT. A positive witness is a satisfying

assignment. A negative witness is e.g. a proof of the negation in

some calculus. Alternatively, a computation establishing the

non-satisfyability can be itself a negative witness. Notice that

negative witnesses may not be long.

3. 3-Colorability Search Problem

Consider the following algorithm

x := min {k>1 : 1 E k};

y := min {k>x : 1 E k & x E k};

z := min {k>y : 1 E k & x E k & y E k}

which fails if any of the three sets is empty

(in which case you may start a "real algorithm" for 3-colorability),

and which outputs "NO" otherwise.

If the probability distribution is uniforme,

the expected # of steps is bounded;

I leave it to you to compute the bound.

4. The Fuzzy Analogy

Fuzzy logic is one of many non-classical logic;

nothing deep about it.

They say, however, that fuzzy control theory has successes.

My mathematical control theory friends hate it:

"Cheating. Optimization requires solving hard mathematical problem."

I disagree: Your application, not its mathematical model,

is the center of interest.

Mathematics is driven by aesthetics, but business by the bottom line.

It is common to analize the average case behavior of a beautiful

algorithm with respect to the given probability distribution.

Alternatively, start with a probability distribution and seek

an appropriate algorithm.

5. The Hamiltonian-Path Search Problem

That is exactly what we did, when we realized that HP with the uniform

distribution is not going to be complete for the average case. We

designed a cascade of three algorithms.

HPA1, quick and dirty, seeks a path.

HPA2, the working horse, seeks a path or

a witness of nonexistence of a path.

HPA3, linear-space relatively fast exhaustive search.

It is harder to analyse a cascade of algorithms. Some events become

known and thus the input is not quite the pristine random structure it

was.

6. Feasible vs. polynomial time

Neither implication is correct.

7. The trouble with complexity theory

It is all assymptotical.