Уже ближе к концу, устав бороться с грудой тусклых слов, он без всякого энтузиазма взялся за очередной не очень толстый пакет от неизвестного ему отправителя из Ленинграда. Для начала стопочка сероватой бумаги порадовала удобной формой подачи материала — короткое резюме на три с половиной страницы и два десятка страниц собственно статьи. А затем… Затем он с головой провалился в текст.

Было захватывающе интересно вместо привычного спуска по вершинам многогранника допустимых решений сжимать внутри фигуры эллипс, быстро сходящийся к искомой внутренней точке. Да еще и погрешности вычисления не накапливаются, самокорректируясь на каждом последующем шаге в конусе центрального пути! Прелесть, просто прелесть этот новый алгоритм! Что-то подобное пытался делать Дикин лет десять тому назад, но подход, предложенный в письме, был куда как более зрелым.

Решение развертывалось перед внутренним взором Канторовича в разных, в том числе и не описанных автором вариациях до тех пор, пока встревоженная затянувшейся тишиной жена не проникла в кабинет с тарелкой бутербродов. Чесночный запах домашней буженины ненадолго потеснил любимый функциональный анализ. Он торопливо вытер замаслившиеся пальцы о полотняное полотенце и взялся за еще непрочитанную страницу с подзаголовком «основная теорема».

«О как! — дочитав, встал и взволновано заходил вокруг стола. — О как! А вот это… Это — уже принципиально. Число операций растет не быстрее, чем полином от объема входных данных. Так-так-так. Нет, ну не обязательно все будет так гладко», — попробовал он остудить свой восторг, — «алгоритм, имеющий лучшую верхнюю оценку сложности, вовсе не обязательно будет наиболее удачен для практической реализации. Симплекс-метод в наихудшем случае экспоненциален, однако для обычных входных данных работает хорошо. Здесь же доказанная полиномиальность в худшем случае. Да, будет очень интересно сравнить практическую эффективность методов. Но, всяко, хорошая гарантированная оценка объема вычислений в ряде случаев очень важна. К примеру, у военных или в космосе в темпе реального времени, когда важно заранее знать максимальное время получения решения с требуемой точностью».

И дальше весь день его мысли, словно магнитом, все время притягивало к этой статье.

«Ах, как обидно, — с досадой восклицал он про себя, — решение валялось у всех на виду как минимум лет тридцать, и толпы математиков дружно промаршировали мимо. А надо было лишь взглянуть под иным углом. Хм… А ведь теперь все линейное программирование стало относиться к классу полиномиально разрешимых задач. А вот это — фундаментально. Это сразу ставит результат в ряд немногочисленных классических.»