Cтраница 3
В этой главе мы приведем соображения, показывающие, что некоторый класс задач, а именно задач, полных для недетерминированного полиномиального времени ( называемых NP-полными), вероятно, содержит только трудно разрешимые задачи. Этот класс включает в себя многие классические задачи из комбинаторики ( такие, как задачу о коммивояжере, о гамильтоновом цикле, задачу целочисленного линейного программирования), и можно показать, что все задачи из этого класса эквивалентны в том смысле, что если хотя бы одна из них оказалась легко разрешимой, то таковы же и все остальные. Поскольку многие из этих задач изучались математиками и специалистами по вычислениям в течение десятилетий и ни для одной из них не удалось найти алгоритма полиномиальной сложности, естественно предположить, что таких полиномиальных алгоритмов и не существует, и, значит, можно рассматривать все задачи из этого класса как трудно разрешимые. [31]
Порядок сложности всех этих алгоритмов был полиномиален. Иногда время их работы оказывалось линейным, как при последовательном поиске: при удлинении списка вдвое алгоритм работает вдвое дольше. Нам встречались и алгоритмы сложности O ( N2) - такую сложность имеют некоторые алгоритмы сортировки: если длину входного списка удвоить, то время работы алгоритма возрастает в 4 раза. Сложность стандартного алгоритма матричного умножения равна O ( 7V3), и при увеличении размеров матриц вдвое такой алгоритм работает в 8 раз дольше. [32]
Существует ли алгоритм, отыскивающий за время 0 ( е) хотя бы кратчайшее расстояние между двумя конкретными точками. Читателю было бы полезно ознакомиться с упр. Джонсона [1973], а также с работой Спиры, Пана [1973], в которой показано, что в общем случае для таких алгоритмов требуется п2 / 4 сравнений, если алгоритмы используют только сравнения между суммами стоимостей ребер. Вагнер [1974] применил технику сортировки вычерпыванием, чтобы получить алгоритм сложности 0 ( е) в случае, когда в качестве стоимостей ребер фигурируют малые целые числа. [33]
Например, позиционное дерево для a bnanbn 1) содержит п2 6п 2 узлов, в чем легко убедиться самим. Но при разумных предположениях о том, что такое случайная цепочка ( например, символы выбираются из алфавита с равной вероятностью и независимо), можно показать, что среднее позиционное дерево для цепочки длины п содержит 0 ( п) узлов. Отметим лишь, что существует алгоритм сложности 0 ( п) в худшем случае, который строит компактную форму позиционного дерева прямо по данной цепочке. Работы, обсуждающие этот алгоритм, указаны в замечаниях по литературе. [34]