Основные понятия теории NP-полноты P NP?

Задачи распознавания свойств Класс задач распознавания свойств (ЗРС) – множество проблем, решением которых является ответ «Да» или «Нет». ГАМИЛЬТОНОВ ЦИКЛ (ГЦ). Задан граф G = (V, E). Спрашивается, содержит ли G гамильтонов цикл? max{f(x) : x D} Opt задаче max{f(x) : x D} соответствует ЗРС: ли решение x D: f(x) Q? « ли решение x D: f(x) Q?», где Q – заданное число. КОММИВОЯЖЕР (КМ). Дано: N – список городов; c ij – расстояния между городами i,j N; B R. ли гамильтонов контур, длина которого B?

Задачи Под общей (массовой) задачей (проблемой) P понимается некоторый общий вопрос, требующий ответа. Общая задача, как правило, содержит некоторые параметры. В задаче КМ, например, это расстояния между городами. Если все параметры общей задачи принимают конкретные значения, то такую задачу называют индивидуальной.

Трудоёмкость алгоритма Количество символов в стандартном (двоичном) представлении данных инд. задачи X P наз. длиной входа и обозначим L(X). наз. трудоемкостью алг. A., где d – целое положительное число Алг., трудоемкость которого не ограничена полиномом от длины входа, наз. экспоненциальным. Пусть алг. A решает проблему P и t A (X) количество элементарных операций, выполняемых алгоритмом A при решении инд. задачи X P. Тогда функция Алг. A наз. полиномиальным, если его трудоемкость

Трудоёмкость алгоритма Пусть n – входная длина. Алг. A 1 решает задачу P с трудоемкостью O(n 5 ). Алг. A 2 имеет трудоемкость O(2 n ) решения задачи P. ЭВМ - 1 млн. опер./сек. Тогда при n = 60 алг. A 1 будет работать около 13 минут, а алг. A 2 – более 300 столетий! Предположим, что A 2 строит решение задачи размерности D на вышеупомянутом компьютере за 1 час. Если взять компьютер, выполняющий в 1000 раз больше операций в секунду, то размерность задачи, которая решается алг. A 2 на таком компьютере в течение 1 часа, будет всего D Полиномиальные алгоритмы – эффективные! Экспоненциальные алгоритмы – не эффективны!

Класс NP При анализе задачи важно знать ли полиномиальный алг. ее решения. Частично на этот ? отвечает теория NP-полноты. Класс NP – это мн. ЗРС, у кот. проверка ответа «Да» для заданного решения осуществляется за полиномиальное время. ЗРС, соответствующие ЗР, КМ, ГЦ, … NP.

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

Класс NPC Первой задачей, NP-полнота кот. была доказана Куком С.А. (Cook S. A.) в 1970 г., является задача ВЫПОЛНИМОСТЬ. Задано мн. N, и 2m его подмн. {C i } и {D i }, i = 1,..., m. ли вектор x B n, удовлетворяющий всем неравенствам Пример: N = {1, 2}, C 1 = {1}, D 1 = {2}, C 2 = {2}, D 2 = {1} m = 2, Нет!

Лемма о сводимости Лемма (О сводимости). Пусть задачи P,Q NP. Тогда: 1) Если Q P и задача P п.с. к Q, то P P. 2) Если P NPC и задача P п.с. к Q, то Q NPC. Доказательство. Утверждение 1) очевидно. Докажем 2). Возьмем произвольную задачу R NP. Т.к. P NPC, то R п.с. к P. Однако P п.с. к Q, и, следовательно, R п.с. к Q. Так как это имеет место задачи R NP, значит Q NPC. Следствие. Если P NPC, то P=NP. Доказательство. Пусть задача Q P NPC, а задача R NP. По утв. 2) Леммы, если Q NPC, то R п.с. к Q. Согласно утв. 1) Леммы, т.к. Q P и R п.с. к Q, то R P. Значит, задача из NP может быть решена за полиномиальное время, т.е. NP P. Но по определению P NP и P=NP.

Доказательство NP-полноты Лемма о сводимости дает удобный способ доказательства NP- полноты задач. Для доказательства принадлежности задачи P NP классу NPC достаточно найти некоторую NP-полную задачу Q и полиномиально свести ее к задаче P. Пример. ГЦ NPC. Покажем, что КМ NPC. Для этого по заданному графу G=(V,E), |V|=m, построим задачу КМ, в которой N=V, c ij =1, (i,j) E и c ij =2, (i,j) E и B=m. Если в КМ цикл длины B («да»), то в G гам. цикл. Если же значение ц.ф. КМ всегда > B («нет»), то в G нет гамильтонова цикла. Очевидно, данное сведение является полиномиальным. если КМ полиномиально разрешима, то и ГЦ P. И, наоборот, если для ГЦ не полиномиального алг., то и КМ не разрешима за полиномиальное время.

Классы P и NP Отношения классов P и NP является открытой в теории NP- полноты. Однако тот факт, что ни для одной NP-полной задачи не найдено полиномиального алгоритма, косвенно подтверждает гипотезу строгого включения P NP, т.е. P NP. P NPC NP

Задача о камнях РАЗБИЕНИЕ. («Задача о камнях»). Задано: мн. A = {a 1, …, a n }; вес s(a i ) Z + ; ли разбиение множества A на 2 подмножества одинакового веса, – четное. т.е. ли А А: =+

Алгоритм Введем Табл. значений t(i,j) заполняется построчно слева направо: t(1,j)=T, когда j=0, или j=s(a 1 ); в строках i=2,…,n для 0 j B/2 значение t(i,j)=T, только в случаях, когда t(i 1,j)=T, или s(a i ) j и t(i 1,j s(a i ))=T. Пример. n=5, s(a 1 )=1, s(a 2 )=9, s(a 3 )=5, s(a 4 )=3, s(a 5 )=8; B=26. j i 1TT 2TTTT 3TTTTTT 4TTTTTTTTTTT 5TTTTTTTTTTTT

Псевдополиномиальные алгоритмы N(X) - max число среди входных данных инд. задачи X P. Алгоритм, строящий решение задачи P, наз. псевдополиномиальным, если инд. задачи X P трудоемкость построения решения ограничена полиномом от 2 аргументов: входной длины L(X) и значения max числового параметра N(X). Инд. задача, у кот. величина N(X) ограничена полиномом от L(X), и для кот. псевдополиномиальный алг., является полиномиально разрешимой.

NP-полнота в сильном смысле Задачу P NP называют NP-полной в сильном смысле (с.с.), если для ее решения не псевдополиномиального алгоритма. К NP-полным в с.с. проблемам относятся все NP-полные задачи без числ. параметров, а также нек. хорошо известные задачи с числ. параметрами (например, задача КМ). Задача о ранце является примером проблемы, кот. может быть решена псевдополиномиальным алг. она не является NP-полной в с.с.

NP-трудные задачи Оптимизационная (экстремальная) задача, для кот. соотв. ей ЗРС NP-полна, является NP-трудной. При решении NP-полной (трудной) проблемы часто применяют полиномиальные приближенные алг. При этом строится доп. решение, и чем оно ближе (по функционалу) к opt решению, тем оно лучше. Теория NP-полноты иногда позволяет очертить возможности приближенных алгоритмов…

Задача о ранце Теорема. Если P NP, то не полиномиального алг. A для решения булевой задачи о ранце (ЗР): с целочисленными неотрицательными параметрами c k и a k, кот. строит решение любой инд. задачи I ЗР с ограниченной const абс. погрешностью: |A(I) – OPT(I)| Q = const. (*)

Доказательство теоремы Предположим противное: полиномиальный алг. A и целое число Q : что инд. задачи I ЗР |A(I) – OPT(I)| Q. Покажем, что тогда алг. А можно использовать для построения оптимального решения ЗР, кот. NP-трудна, что противоречит условию P NP. Каждую инд. з. I можно свести к задаче I заменой параметров c k на (Q+1)c k. Применим алг. A к задаче I. Очевидно, выполнение следующих свойств: – величина А(I ) кратна (Q+1); – OPT(I )=(Q+1)OPT(I). Т.к. при сделанном предположении неравенство (*) вып. инд. задачи, то |А(I ) – OPT(I )| Q. |А(I ) – OPT(I )|=|А(I ) – (Q+1)OPT(I)| Q. А(I )=(Q+1)OPT(I)=OPT(I ).

Задача коммивояжёра Теорема. Если P NP, то не полиномиального алг. A решения задачи КМ с относительной погрешностью ограниченной const. Т.е. не const K: I КМ Доказательство. Предположим, что const K > 0: I КМ справ. (*). Покажем, что тогда задача ГЦ полиномиально разрешима. Пусть инд. задача ГЦ задана графом G=(V, E), n=|V|. Построим инд. задачу I КМ след. образом. Пусть V – мн. городов, а расстояние: (*) Применим алг. A к I. Если в G гам. цикл, то OPT(I)=n. В пр. сл. OPT(I)>Kn. неравенство A(I) Kn в G гам. цикл. из полиномиального алг. А, с описанными выше свойствами, полиномиальная разрешимость ГЦ…