8_2 (1019128), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

Компьютерные науки делают пока только первые шаги в классификации задач по сложности. Естественно, что начинаем с дихотомии: попытки разделить все задачи на два класса – легкие и трудные. Границу между ними можно проводить по-разному, но все сошлись во мнении, что задачи, для решения которых требуется выполнить O(n), O(n²), O(n³), … операций – это легкие задачи (здесь n –параметр сложности исходных данных). Задачи же с оценкой сложности 0(2ⁿ) и более — сложные. Первую груп­пу задач называют задачами полиномиальной сложности, поско­льку их временная сложность ограничивается сверху некоторым полиномом (быть может, очень большой, но конечной степени п). Обозначим множество таких задач Р. Вторую группу называют задачами экспоненциальной сложности, поскольку в общем случае (т. е. для исходных данных, наиболее «неудобных» для любого из алгоритмов, решающих задачу) требуется количество операций, увеличивающееся с ростом п по крайней мере экспоненциально. Обозначим множество этих задач ЕХР.

Такое разграничение практически оправдано. Представим себе, что на самом быстром из доступных нам компьютеров ре­шаем две задачи, полиномиальную Р₁ с параметром сложности исходных данных n₁ и экспоненциальную Р₂ с параметром n₂. Эти две задачи решаются примерно одинаковое время Т и находятся на грани того, чтобы испытывать наше терпение: согласны ждать время Т, но ни секунды больше! И вот, наконец, мы получили но­вый компьютер, работающий в несколько (k) раз быстрее, чем старый. Вопрос: насколько более сложные задачи можно решать на новом компьютере (как изменятся n₁ и n₂ ?), если наши воз­можности ожидания решения не изменились ?

Простой анализ показывает, что доступная сложность поли­номиальной задачи увеличилась в несколько РАЗ, стала равной m*n₁, а доступная сложность экспоненциальной задачи увеличилась НА несколько ЕДИНИЦ, стала равной п₂ + l. Здесь m и l вычисляются через k. Например, если первая задача имеет линейную сложность, а вторая — 2ⁿ, то ускорение компьютера в два раза (k = 2) приводит к значениям 2n₁, и n₂ ⁺ 1. Это действите­льно качественно различные результаты.

Известны многие представители класса задач полиномиаль­ной сложности: вычисление скалярного произведения векторов, произведение матриц, решение системы линейных уравнений, сортировка массива чисел, вычисление наибольшего общего де­лителя, вычисление факториала, ... Хотелось бы, чтобы все зада­чи были легкими, но сегодня для ряда задач известны только экс­поненциальные алгоритмы! В связи с попыткой классификации сразу возникает много вопросов. Существуют ли неполиномиа­льные задачи или для любой задачи может быть построен поли­номиальный алгоритм? Если существуют, то где проходит грани­ца между полиномиальными и неполиномиальными задачами, как ее описать (иными словами, найти легко вычислимую характеристическую функцию множества Р)?

Изобразим условно взаимоотношение классов задач полино­миальной и экспоненциальной сложностей (рис. 8.3).

Рис. 8.3. Сложность некоторых задач

Здесь каждая точка области, ограниченной прямоугольни­ком, представляет некоторую задачу. Две точки — это примеры задач из разных классов. Выше было выяснено, что для переноса «Ханойской башни» требуется 0(2ⁿ) операций, а для перемноже­ния матриц не более, чем 0(n³) операций. О третьей точке — за­даче ВЫПОЛНИМОСТЬ — речь пойдет ниже.

Где проходит граница между классами задач полиномиаль­ной сложности Р и экспоненциальной сложности ЕХР ? Ответ на этот вопрос, т. е. описание границы (например, задачи с таки­ми-то свойствами входят в класс Р, а все остальные входят в класс ЕХР) в настоящее время не известен. Чтобы разведать гра­ницу, математики придумали еще один класс задач — NP. Интуи­тивно предполагается, что он может оказаться «нарушителем границы». Это класс задач, которые можно решить за полиноми­альное время (Р), но на машине, более мощной, чем обычная од­нопроцессорная машина — на недетерминированном (N) вычис­лителе. Недетерминированный вычислитель исполняет так называемые недетерминированные алгоритмы. Напомним свой­ство детерминированности определенность (детерми­нированность) алгоритма означает, что для каждого шага могут быть по набору исходных для шага данных однозначно вычисле­ны результаты выполнения шага и эти результаты не зависят ни от каких случайных факторов. Соответственно этому и алгоритм в целом по окончании работы исполнителя выдает вполне опре­деленный результат.

Недетерминированный алгоритм лишен этого свойства. Раз­решаем шаги с неоднозначным результатом — шаги, вырабатывающие сразу несколько значений для одной и той же перемен­ной. Эти несколько значений далее могут быть использованы одним из двух способов.

Первый способ. Создать несколько параллельно выполняю­щихся процессов (по процессу для каждого значения) для про­должения вычислений. Это возможно на многопроцессорной ма­шине с неограниченно большим количеством параллельно работающих процессоров.

Второй способ. Угадать, какое из нескольких значений, полу­ченных на данном шаге, является правильным (задающим ис­комое решение) и использовать в дальнейшем только его, иг­норируя все остальные. В этом случае требуется только один процессор, но дополненный угадывающим устройством.

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

Задача о переносе «Ханойской башни» по самой постановке не может быть распараллелена, так как в один момент времени только один диск переносится с иглы на иглу. Поэтому, даже при появлении такой мощной техники как недетерминированные ма­шины эта задача остается в классе ЕХР.

Задача, решаемая за полиномиальное время на обычной ма­шине, может быть решена за полиномиальное время и на неде­терминированной машине, т. е.

P  NP.

Верно ли обратное (и тогда Р = NP) или существуют задачи, решаемые за полиномиальное время на недетерминированной машине, но требующие экспоненциального времени на однопро­цессорной машине (тогда Р  NP, NP \ Р  ) ?

В первом случае ничего нового в классификации задач от вве­дения класса NP не получим. Но появляется много надежд. Дело в том, что для некоторых задач из класса NP известны только эк­споненциальные алгоритмы для их решения на однопроцессор­ной машине. Если Р = NP, т. е. надежда разработать и полиномиальные алгоритмы. Вопрос этот не праздный. На карту поставлено не только машинное время. В криптографии (науке о шифровании информации) существует целое направление — шифрование с открытым ключом. В его основе использование математических задач, решаемых алгоритмами экспоненциаль­ной сложности. Если вдруг для них найдутся эффективные поли­номиальные алгоритмы, то многие секреты перестанут быть сек­ретами.

Но и во втором случае появляется много вопросов. Что собой представляет класс NP \ Р ? Чем задачи из этого класса отличают­ся от других задач из ЕХР? В настоящее время развита довольно большая теория задач класса NP в предположении, что NP  Р. Кому-то может показаться, что это сродни теории привидений. Не известно, есть ли привидения, а уже обсуждается их одежда, вкусы, походка и любимый род занятий.

Однако такой взгляд не верен. Нерешенная проблема не должна тормозить развитие науки. В математике, в компью­терных науках существует несколько недоказанных (или недо­казуемых) фундаментальных утверждений-гипотез, принятие которых позволило получить большое количество важных результатов. Достаточно вспомнить тезис Тьюринга, тезис Черча

Введем еще один класс задач - NP-полные (NPС задачи (проблемы). Проблема Т называется NP-полной, если она удов­летворяет двум условиям:

1) Т  NP;

2) Если R  NP то R сводится к T за полиномиальное время.

NP-полные проблемы являются своего рода универсальными. Не нужно придумывать алгоритмы для других задач, достаточно свести эти задачи к какой-либо NP-полной проблеме и воспользоваться алгоритмом ее решения.

С тех пор как С. Кук доказал в 1971 г., что проблема выпол­нимости для пропозиционального исчисления является NP-полной, множество NPC пополнилось сотнями проблем.

NP-полные проблемы, как следует из определения, являются наиболее трудными в классе NP.

Значение класса NP-полных проблем состоит еще и в том, что ему принадлежат очень многие известные и важные в приклад­ном отношении задачи. Перечислим некоторые из них.

1. Задача изоморфизма подграфу.

Даны два графа, G₁ и G₂. Множество вершин первого графа обозначим V₁, а второго — V₂ . Пусть |V₁| > | V₂| = п. Требуется ответить на вопрос: найдется ли в графе G₁ подграф H, изоморф­ный графу G₂?

2. Задача о клике.

Дан граф G с m вершинами и целое положительное число п. Граф называется кликой, если каждая вершина в нем связана реб­ром с каждой. Количество вершин в клике назовем ее мощно­стью. Верно ли, что в данном графе G имеется клика мощности не менее, чем n?

3. Гамильтонов цикл.

Дан граф G c n вершинами. Существует ли в графе простой цикл, проходящий через все вершины графа? Простым называет­ся цикл, в котором вершины не повторяются. Таким образом, гамильтонов цикл — это последовательность вершин и дуг (ребер) графа, содержащая все вершины графа G по одному разу, но, мо­жет быть, содержащая не все дуги.

4. Задача коммивояжера.

Дан граф G с п вершинами. Каждому ребру графа приписано положительное целое число d_i , задающее длину ребра. Кроме этого, задано некоторое положительное целое число L. Требует­ся ответить на вопрос: найдется ли в графе G маршрут, проходя­щий через все вершины графа G , такой, что его длина не превы­шает L?

Другие модификации задачи о коммивояжере требуют отыскания маршрута минимальной длины, гамильтонова цикла и т. п. Неизменным остается требование однократного прохождения че­рез все вершины.

Кроме класса NP-полных проблем рассматривают еще и класс NP-трудных проблем.

Проблема Т называется NP-трудной, если она удовлетворяет условию: Если R  NP, то R сводится к T за полиномиальное вре­мя.

Заметим, что это условие совпадает со вторым условием для NP-полных проблем. Следовательно, NP-полная проблема — это NР-трудная задача, принадлежащая классу NP.

Для того чтобы уяснить себе возможное различие между классами Р и NP, продолжим анализ проблемы выполнимости логического выражения.

Кроме общей задачи о выполнимости, могут быть поставле­ны задачи с ограничивающими условиями. Например, ограниче­ние на длину дизъюнктов.

Задача о k-выполнимости — это задача о выполнимости для выражений, в которых длины дизъюнктов не превосходят вели­чины k.

Р азумеется задача о k-выполнимости проще задачи о (k + 1)-выполнимости, и проще общей задачи о выполнимости для лю­бого конечного k. Самая простая — задача об 1-выполнимости. В этом случае любой дизъюнкт состоит только из одной пере­менной или ее отрицания, т. е. Если все переменные в записанной конъюнкции различны, то выражение выполнимо, а если одна и та же переменная встречается два раза, в одном случае с показателем 1, а в другом случае с пока­зателем 0, то в соответствии с известным тождеством х¹&х° = 0 выражение тождественно равно нулю, т. е. не выполнимо. Про­верка этого требует времени, линейного по отношению к длине выражения.

Вывод: задача об 1-выполнимости принадлежит классу Р.

Характеристики

Список файлов книги