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.