Задач распознавания свойств (зрс)

ВЫПОЛНИМОСТЬ. Задано мн. N, и 2m его подмн. {Ci} и {Di},

i = 1, ..., m.

 ли вектор x  Bn, удовлетворяющий всем неравенствам

• Пример: N = {1, 2}, C1 = {1}, D1 = {2}, C2 = {2}, D2 = {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, cij=1, (i,j)E и cij=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 = {a1, …, an};
• вес s(ai)  Z+;

•  ли разбиение множества A на 2 подмножества одинакового веса,

• – четное.

• т.е.  ли А  А:

• =

• +

• Алгоритм

• Введем

• Табл. значений t(i,j) заполняется построчно слева направо:
• t(1,j)=T, когда j=0, или j=s(a1);
• в строках i=2,…,n для 0 jB/2 значение t(i,j)=T, только в случаях, когда t(i1,j)=T, или s(ai)j и t(i1,js(ai))=T.

• Пример. n=5, s(a1)=1, s(a2)=9, s(a3)=5, s(a4)=3, s(a5)=8; B=26.

j

0

1

2

3

4

5

6

7

8

9

10

11

12

13

i

1

T

T

2

T

T

T

T

3

T

T

T

T

T

T

4

T

T

T

T

T

T

T

T

T

T

T

5

T

T

T

T

T

T

T

T

T

T

T

T

• Псевдополиномиальные алгоритмы

• 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 для
• решения булевой задачи о ранце (ЗР):

• с целочисленными неотрицательными параметрами ck и ak, кот. строит решение любой инд. задачи IЗР с ограниченной const абс. погрешностью:
• |A(I) – OPT(I)|  Q = const. (*)

• Доказательство теоремы

• Предположим противное:  полиномиальный алг. A и целое число
• Q : что  инд. задачи IЗР |A(I) – OPT(I)|Q. Покажем, что тогда
• алг. А можно использовать для построения оптимального
• решения ЗР, кот. NP-трудна, что противоречит условию PNP.
• Каждую инд. з. I можно свести к задаче I заменой параметров
• ck на (Q+1)ck. Применим алг. 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  гам. цикл.  из  полиномиального алг. А, с описанными выше свойствами,  полиномиальная разрешимость ГЦ…