Журнал «Компьютерра» № 6 от 14 февраля 2006 года

Наверное, мало кто из людей, связанных с компьютерной индустрией, не слышал об этой задаче, занимающей центральное место в современной теоретической (и практической) информатике. За применениями ее возможного решения далеко ходить не нужно – они так разнообразны, что вряд ли мне удастся изложить их все. P и NP, за выяснение факта равенства или неравенства которых платят миллион – это так называемые сложностные классы алгоритмов. Понятие сложности алгоритма совсем не такое сложное, как некоторые алгоритмы. Попробую изложить его здесь более или менее строго, потратив на это константное время (сейчас поймете, что это такое) – как свое, так и читателей.

Предельно коротко и нестрого (зато интуитивно) классы P и NP можно описать так: P – это вычислительные задачи, которые легко решить; NP – задачи, для которых легко проверить, верно ли предполагаемое решение. Перейдем к более точным формулировкам.

Начнем с моделей вычислений. Математические модели компьютеров появились раньше, чем сами электронно-вычислительные машины, но задержка оказалась небольшой. В 1936 году Эмиль Пост (Emil Leon Post), а в 1937 году – Алан Тьюринг (Alan Turing) независимо друг от друга разработали теоретическую модель, которая легла в основу теории алгоритмов. Первый программируемый компьютер – механический агрегат под названием Z3 – был создан уже в 1941 году[ЭНИАК – отнюдь не первый компьютер. Сам ЭНИАК был завершен в 1946 году, но в то время программа, по которой он действовал, была «зашита» в железо, и для перепрограммирования ЭНИАКа нужно было менять его схемы]. Идеальный компьютер очень прост (таково общее свойство большинства полезных математических моделей). Он представляет собой бесконечную в одну сторону (пусть справа) ленту, по которой бегает одна-единственная головка. В каждой ячейке ленты может стоять ноль, единица или не стоять ничего. На каждом шаге выполнения алгоритма головка может сдвинуться влево, сдвинуться вправо либо записать в ячейку, над которой она находится, ноль или единицу. Программа для такой машины – это сколь угодно большой, но конечный набор состояний, каждому из которых соответствует некоторое действие, а также следующее состояние. Есть два выделенных состояния – исходное, в котором начинается работа программы, и специальное состояние СТОП, которое соответствует выходу из программы. Например, вот простая программа:

состояние 0:

прочесть то, что находится под головкой: если 0, перейти в состояние 1; если 1, перейти в состояние 2; если пусто, перейти в состояние СТОП;

состояние 1:

записать в текущую ячейку 1 и перейти в состояние 3;

состояние 2:

записать в текущую ячейку 0 и перейти в состояние 3;

состояние 3:

сдвинуть головку вправо и перейти в состояние 0.

Она бит за битом инвертирует двоичную строку, записанную на ленте (считаем, что изначально головка находится в крайней левой ячейке, с которой начинается запись числа), а когда строка заканчивается, заканчивает работу и программа.

Эта модель вычислений, получившая название машины Тьюринга, стала общепринятой (хотя Пост придумал свою модель на год раньше). На первый взгляд такой простой объект кажется недостаточным для того, чтобы описать все многообразие компьютерных архитектур, – но пока не известно ни одного алгоритма, который нельзя было бы реализовать на машине Тьюринга. В логике и информатике широко известно нестрогое утверждение (так называемый тезис Черча), которое гласит, что любой объект, отвечающий нашему интуитивному понятию алгоритма, можно реализовать в виде программы на машине Тьюринга. Контрпримеров к этому утверждению пока не обнаружено, и оно считается верным – хотя доказать его, разумеется, невозможно.

Теперь нам нужно научиться оценивать скорость работы различных алгоритмов, сравнивать их друг с другом. Один и тот же алгоритм будет на «Пентиуме» работать несравненно быстрее, чем на машине Тьюринга. Более того, процессор современного компьютера может получить данные из любой ячейки памяти, просто «заказав» соответствующей шине адрес ячейки. А единственной головке машины Тьюринга, чтобы добраться до далеких данных, нужно шаг за шагом пройти всю ленту… Неужели эти изменения не влияют на теоретические оценки времени работы алгоритма?