logo
shpori (1) / shpori (1)

21. Классы p и np. Полиномиальное сведение.

Задача называется полиномиально разрешимой, если существует машина Тьюринга, решающая эту задачу за полиномиальное время(если существует алгоритм ее решения с полиномиальной временной сложностью)

P – класс полиномиально разрешимых задач.

P – класс задач которые можно эффективно решить

Для каждой задачи по крайней мере можно проверить, является ли данный ответ решением задачи

Волшебник Мерлин дает подсказку Королю Артуру, а король проверяет за полиномиальное время

Задача А, Недетерминированный алгоритм

Пусть А – задача, Х – некоторые входные данные задачи А

Будем говорить, что Артур и Мерлин решают задачу A,если для любых X

1)если X – положительное решение, то существует подсказка Мерлина, которая убедит Артура в том, что X – положительное решение;

2)если X – отрицательное решение, то никакая подсказка не убедит Артура в обратном.

Недетерминированный полиномиальный алгоритм

Артур и Мерлин решают задачу А за полиномиальное время O(q(n)), если для любого Х

1) , 2)

3)время обработки Артуром любой подсказки Мерлина не превосходит O(q(n))

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

Т-ма. Если задача А принадлежит классу NP, то существует детерминированный алгоритм трудоемкости О(2р(n)), решающий эту задачу, где р(n) – некоторый полином

Доказательство. Пусть вход X задачи A закодирован в виде последовательности 0 и 1.

Так как AÎNP, то верно следующее: если X-положительное решение, то существует подсказка Y такая, что Артур по паре (X,Y) за полиномиальное время, ограниченное r(n), убеждается в том, что X – положительное решение (где r(n)-полином) |Y| £ r(n)

Сколько всего различных подсказок длины r(n) ? 2r(n)

Алгоритм:

for (все возможные подсказки Y длины r(n))

{ применить алгоритм полиномиальный

алгоритм Артура к паре (X,Y);

if (Arthur(X,Y) == true)

return true;}

return false.

Трудоемкость алгоритма – 2r(n)*r(n) = O(2p(n))

Полиномиальное сведение

Пусть A и B – две задачи. Будем говорить, что A полиномиально сводится к B,если существует полиномиальный алгоритм, преобразующий любые входные данные X задачи A во входные данные YX задачи B таким образом, что X – положительное решение A тогда и только тогда, когда YX – положительное решение B. В этом случае мы пишем AB (сводимость по Карпу). Пусть AB, если В полиномиально разрешима, то и А полиномиально разрешима. Задача называется NP-полной, если к ней полиномиально сводится любая задача из NP.

“Гамильтонов путь” µ “Гамильтонов цикл”