Читать «Журнал «Компьютерра» № 6 от 14 февраля 2006 года» онлайн - страница 91
Компьютерра
Надеюсь, к моменту выхода окончательной версии GPL3 этот вопрос, как и многие другие, будет решен.
Наука: Проблемы 2000 года: P=?NP
Наверное, мало кто из людей, связанных с компьютерной индустрией, не слышал об этой задаче, занимающей центральное место в современной теоретической (и практической) информатике. За применениями ее возможного решения далеко ходить не нужно – они так разнообразны, что вряд ли мне удастся изложить их все. 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.
Она бит за битом инвертирует двоичную строку, записанную на ленте (считаем, что изначально головка находится в крайней левой ячейке, с которой начинается запись числа), а когда строка заканчивается, заканчивает работу и программа.
