Сводимость задач и ее свойства

Класс P (полиномиальных задач распознавания) – множество з адач распознавания, для которых существует полиномиальный детерминированный алгоритм решения.

Класс NP (недетерминировано полиномиальных задач распознавания) – множество задач распознавания, для которых существует полиномиальный недетерминированный алгоритм решения. Очевидно включение P Í NP, поскольку детерминированный алгоритм по определению является недетерминированным. Но есть много причин считать это включение строгим. Полиномиальные недетерминированные алгоритмы определенно оказываются более мощными, чем полиномиальные детерминированные, и не известны общие методы их превращения в детерминированные полиномиальные.

Если P не совпадает с NP, то различие между P и NP-P очень существенно. Все задачи из P могут быть решены (детерминированными) полиномиальными алгоритмами, а все задачи из NP-P труднорешаемы, и математическим уточнением понятия переборная задача распознавания служит задача из NP-P. В исследованиях проблемы P ¹ NP важное положение занимает понятие полиномиальная сводимость, используя ранее введенное понятие (и обозначение) сводимости - задача A полиномиально сводима к задаче B, если A μp(n)B для некоторого полинома p(n). Задача A называется NP-полной, если A Î NP и для любой другой задачи B Î NP имеет место полиномиальная сводимость B к A. Честь быть «первой» NP-полной задачей выпала на долю задачи распознавания выполнимости формул булевой логики. Кук С.А. показал как формулами булевой логики можно описать работу любой программы недетерминированного вычислителя и на этой основе доказал полиномиальную сводимость любой NP задачи к задаче о выполнимости. Методом (полиномиального) сведения на сегодняшний день доказана NP-полнота обширнейшего семейства задач в различных областях: в булевой логике, в теории графов, в арифметике, при разработке сетей, в теории множеств и разбиений, при хранении и поиске информации, при планировании вычислительных процессов, в математическом программировании, в алгебре и теории чисел, при создании игр и головоломок, в теории автоматов и языков, при оптимизации программ, в биологии, в химии, физике и т.п.

Оригинальные идеи Кука оказались удивительно плодотворными. Они позволили свести много разнообразных вопросов о сложности в единый вопрос: «Верно ли, что NP- полные задачи труднорешаемы?»__

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

Прежде всего, воспользуемся рассуждением известным как «разделяй и властвуй». Оно довольно часто дает хорошие алгоритмы, к тому же хорошо согласуется с нашими намерениями – при таком рассуждении сегменты будут перебираться в другом довольно изощренном специфическом порядке. Рассмотрим следующее сведение исходной задачи к подзадачам - сегмент с максимальной суммой находится:

§ либо в левой половине исходного вектора, § либо в правой его половине,

§ либо левый его конец находится в левой половине, а правый его конец - в правой.

Осталось только выбрать максимальное из решений этих трех подзадач. Рассмотрим параметризированный вариант исходной задачи – найти максимальную сумму по всем сегментам в сегменте x[i..j], и оформим в виде рекурсивной функции maxsofar решение этого варианта исходной задачи. Будем считать, что у нас имеется функция maxsofar3, которая решает третью подзадачу. Будем считать n степенью двойки, это позволит устранить технические детали, которые отвлекают от основных рассуждений, но не вносят каких-либо важных изменений в наши рассуждения. Тогда решение исходной задачи получим вызовом

maxsofar(0,n-1).

FUNCTION maxsofar(i,j:INTEGER):REAL; BEGIN

IF i>j THEN maxsofar:=0 //сегмент пустой

ELSE IF i=j THEN maxsofar:=max(0,x[i])//сегмент одноэлементный

ELSE BEGIN m:=(i+j+1) DIV 2; //находим середину

max1:=maxsofar(i,m-1); //решаем левую подзадачу

max2:=maxsofar(m,j); //решаем правую подзадачу

max3:=maxsofar3(i,j,m); //решаем третью подзадачу

maxsofar:=max(max1,max2,max3)

END END

Теперь рассмотрим третью подзадачу maxsofar3(i,j,m) – найти максимальную сумму по

всем сегментам {[l..u]/i≤l<m≤u≤j}.

Эта максимальная сумма равна сумме двух максимальных сумм:

§ по всем сегментам с правым концом (m-1): {[l..(m-1)]/i≤l<m}

§ и по всем сегментам с левым концом m: {[m..u]/m≤u≤j}

FUNCTION maxsofar3(i,j,m:INTEGER):REAL; BEGIN

maxL:=0; sum:=0; FOR k:=m-1 DOWNTO i DO

BEGIN sum:=sum+x[k]; maxL:=max(maxL,sum) END;

maxU:=0; sum:=0; FOR k:=m TO j DO

BEGIN sum:=sum+x[k]; maxU:=max(maxU,sum) END;

maxsofar3:= maxL+maxU END

Время работы этой программы T3(j-i+1)=O(j - i +1).

Теперь оценим время работы программы 5.3. Для алгоритмов, основанных на рассуждении сведением к подзадачам, оценка времени работы естественным образом описывается рекуррентными соотношениями. В частности в нашем случае: T(n)= 2*T(n/2)+T3(n), где T(n/2) – время решения для первых двух подзадач (левой и правой), а T3(n)=O(n) - время решения третьей подзадачи. Вообще-то надо еще добавить константу для вспомогательных действий и сборки общего решения, но можно считать, что это включено в T3(n). Теперь остается решить это рекуррентное соотношение. Техника решения подобных рекуррентных соотношений достаточно хорошо разработана. Общую ситуацию (охватывающую наш случай) описывает теорема Теорема [4 п.4.3.]. Пусть a ³ 1 и b > 1 - константы, f (n) - функция, T (n) определена при неотрицательных n формулой T(n) = aT (n / b) + f (n)

Где под n / b понимается или én / bù или ën / bû. Положим d a b = log. Тогда:

1) если f (n) = O(nd -e b) для некоторого e > 0, то T(n) = Q(nd);

2) если f (n) = O(ndb), то T(n) = Q(nd log n);

3) если f (n) = O(nd +e b) для некоторого e > 0 и если af (n / b) £ cf (n) для некоторой константы c <1 и достаточно больших n, то T (n) = Q(f (n)).

Как уже отмечалось разбиение задачи на подзадачи с соответствующим решением подзадач и последующей сборкой из результатов их решения общего решения исходной задачи довольно часто эффективно используемая техника. При этом общее время работы алгоритма обычно складывается из суммы времен решения каждой из подзадач T(з1) и T(з2) и времени на формирование общего результата Т(з1 U з2). Как показывает эта теорема, выбором подходящего разбиения на подзадачи с соответствующими параметрами удается минимизировать общее время решения задачи.

Для случая нашей задачи имеем a = b = 2 и d = 1, согласно пункту 2 получаем T (n) = Q(n log n). Итого, мы получили алгоритм существенно лучше, чем предыдущие, причем из полученной оценки времени следует очень важное следствие - программа 5.3 решает исходную задачу, но просматривает не все сегменты входного вектора, поскольку общее количество этих сегментов O(n2). Сейчас видимо было бы полезно проанализировать какие сегменты эта программа не просматривает и на каком основании относит их к бесперспективным. Но мы попытаемся проанализировать возможности исключения сегментов из рассмотрения, опираясь на несколько иное рассуждение. Дело в том, что «разделяй и властвуй» - это один из вариантов рассуждения сведением к подзадачам, при котором исходная задача сводится к двум (или нескольким) подзадачам и сборке общего решения, при этом исходная задача разбивается на две такие же, но примерно половинного размера. Сбалансированное разбиение обычно и дает хороший эффект по времени. С другой стороны, рассуждение методом последовательны уточнений тоже можно трактовать как рассуждение сведением к подзадачам, только разбиение осуществляется скорее наоборот – запредельно разбалансированное: на «почти всё» и «уточняющее дополнение». Представляется, что проанализировать возможности «отбраковки» бесперспективных сегментов на шаге «уточнения» будет легче.