From the letter by G.M. Adel’son-Vel’skii to A.P. Ershov        June 1979

Dear Andrei Petrovich!

Unfortunately, I still haven’t received anything concerning the algorithms symposium. I would be
glad to participate, but I am not sure that I will be able to get authorization by my Institute for a
business trip not scheduled in advance. In any case, I will try to do it. I am very interested in the
issues concerning points 3,4,7, and partly 6. Besides, I am an old enthusiast of history including the
history of science. However I know little about Al-Khorezmi, but I hope that it will not be the
reason for my expulsion from the algorithmist forum. I hope to use the symposium to end with my
Al-Khorezmi illiteracy. I would rather expand the statement of a question. To my understanding it
should be formulated as follows:

a)      Do there exist algorithmic problems that nevertheless must be solved? (Unintentional
plagiarism from “Monday Starts on Saturday”).

b)      What correlation is between the notions of algorithmically unsolvable and universal
problems, or, more generally – between algorithmically unsolvable problem and a problem
for which only infinitely complex algorithms are known?

c)      What should one do in the face of a single or even mass problem, if it should be solved and
only far too complex algorithms are known for its solution?

With regard to point c) I have some hypotheses on possible approaches that can be brought up in
non-committal discussion, and an article on one of these approaches. The latter I would like to
present. Its main results are published in the book “Games Programming” by myself, Arlazarov and
Donskoy. The point is that there are algorithms that give correct solution with high probability
approaching 1 with growth of the algorithm’s complexity (such algorithm has a parameter whose
increase causes complexity growth). Our work (We started it together with Arlazarov and later two
our disciples joined us) deals with selecting a move in a game for two players with full information
and restricted search.

The issue 6 is also interesting, but it is not clear to me whether the languages in question are non-
algorithmic ones like natural languages, or formal ones (I know nothing about non-algorithmic
informal languages, because an algorithmic language is not necessarily a statement language).

What for the issues not mentioned in the preliminary list, to my opinion the situation with universal
problems is worth talking over at the symposium. One can imagine ways of quest for exponential
algorithms for such problems, but the opinion of the majority is that such algorithms do not exist. At
the same time, it is absolutely unclear how one could prove it. Usual informational complexity
evaluations are useless.

And in the end I have one personal matter to discuss. Although the symposium is to be of rather
restricted membership, it seems to me that it would be highly advisable to invite Alexander V.
Karzanov (he is now well known abroad). His latest achievement is in formulating necessary and
sufficient conditions for multi-production flow problem to be solved in a non-directed network by
methods generalizing the classical ones, i.e. conditions for the so called obstructions to flow increase
to be cut-sets. To do this it is necessary to consider requirements graph whose edges connect the
product’s production and consumption poles. To ensure the problem to be cut-set in the graph
complementary to requirements graph, it is necessary that no node should belong to three different
maximal cliques (that is the necessary and sufficient condition). A.V. Karzanov works with me at
VNIISI.

…

                                                                                                                     G.M. Adel’son-Vel’skii