Informatics Award for a native of the USSR

Prize Donald Knuta For 2012 , awarded Leonid Anatolyevich Levin , a native of Dnepropetrovsk , a graduate Moscow State University , a now Professor of Boston University ( state Massachusetts , USA ).

This award for an outstanding contribution to the foundations of computers has been awarded since 1996 under the auspices of two very representative international organizations - the Association of Computing Technology and the Computer Society of the Institute of Engineers in Electrical Engineering and Electronics ( www.sigact.org/prizes/knuth/ ). The material component of the award is $ 5,000. This amount does not affect the reader’s imagination, and the event may seem ordinary, since there are a great many bonuses and there is no way to keep track of everyone.

Meanwhile, each Knuta Prize is a very outstanding event for everyone who is at least a little oriented in modern computer science and programming. The fact is that Donald Knut is now a healthy scientist, the author of the multi -volume essay “The Art of Programming”, which almost all programmers of our time studied and study. He gave scientists to all specialties the famous Tex and Metafont programs for the preparation of articles with scientific symbols, giving an example of disinterested service to the work of science and education. Seeing your name in the list of Knut Prize holders is a rare honor for any computer scientist.

The Knuta Prize is given for the general contribution of the scientist to science, and not for a separate vivid achievement. The award formula notes for four decades of Levin’s future studies in the theory of complexity, cryptography and information theory. It is indicated that Leonid Levin is known for the discovery of the NP-fullness-a core concept of computational complexity. This discovery was made by Levin in the USSR in 1971 independently and almost simultaneously with Stefan Cook. Cook Theorem - Levina entered all textbooks on computer complexity. The task formulated in connection with it P = NP opens a list of the famous problems of the millennium of the Clay Institute.

The scientific director of Levin was Academician Andrei Nikolaevich Kolmogorov. It was not possible to organize the defense of the candidate dissertation prepared by Levin in 1971. The fact is that in the CCCR of those years, Levin’s independence was interpreted as political unreliability, and in the mathematical world of the country there was anti -Semitic sentiments. Kolmogorov asked his comrade Academician Sergei Lvovich Sobolev, director of the Institute of Mathematics of the Siberian Branch of the Academy of Sciences, and defend the candidate dissertation of Levin in Novosibirsk. The consent was given, but the dissertation was completely unexpected for Sobolev, not in no matter what the positive reviews of N.A. Shanina, B.A. Trachtenbrot and J. Bardzin.

A striking manner against the dissertation was opposed by a scientist who was especially close to Levin's problems. The defense stated the ambiguity of Levin’s “political appearance” - mathematical nasty things have already reached the capital to Siberia. Levin did not become a candidate of sciences, and the attitude towards him from the part of those who emerge after these events left much to be desired.

Describing that time, Levin noted: “I became a burden for everyone with whom I was connected; It became impossible for me to work in serious scientific institutions and even embarrassed to go to seminars (the participants were asked to report my visits). My existence in Moscow began to look meaningless. ” Levina survived from mathematics and from the country.

However, the outstanding Odyssey Levin successfully continued in the United States, where he immigrated in 1978 and where he had conditions for happy work and life. Here he developed the theory of NP-fullness on average. This theory is still in the best way to explain why the bad computing tasks are not found in special situations, but “on average” in the conditions of a fairly accidental set of source data.

Levin’s achievement on American land is very impressive. Levin, Laszlo of the Babai, Lance Fordnau and Mario Shegged belongs to the concept of “holographic evidence”, the truth of which can be established by a check of small pieces. It is worth noting that Levin and his colleagues managed to solve many riddles of modern cryptography.

There are many reasons to congratulate Leonid, rejoice for him and for world science. But one cannot get rid of the feeling of bitterness for the fact that the intellectual potential of our compatriot was not in demand in his homeland, but caused envy and rejection. Xenophobia bacilli, self -praise and isolation from the world community in scientific life are indestructible. As in medicine, you cannot do without sanitation in science.

Semyon Kutateladze