Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 80

Таким образом, результаты зависят от того, «как повезете с выбором значений этих переменных на каждом шаге. !!!'Р-полные задачи, Уже говорилось, что после конца процесса элементарных логических операций результаты вычислений, записанные в ячейках памяти машины с номерами 1, 2, ..., т — 1 (т — длина программы' машины элементарйых логических операций) и являющиеся значениями переменных з!, гь, г, !, соответственно удовлетворяют одной из следующих систем логических уравнений: 1) зс=оь если !-я команда имеет вид !: !: ='с;; 2) г;=зь если она имеет вид !: !': (; 3) зг= )гь когда это — операция отрицания с:!: = 1у; 4) .г!=г!У!зы з! = з!'!/гы если это соответственно операции !; !:=/Ы, или !: !: = = 1'!/й;. Если программа элементарных логических операций предопределяет результаты, то значения всех переменных 25' г;(1=1, 2, ..., т — 1) однозначно находятся из этой системы, но при интерпретации ветви вычислений недетерминированной машины Тьюринга результаты не определены однозначно, так как переменные гь которым соответствуют выборы ветвей д«(6=1, 2, ..., 1) на 1-м, 2-м, ..., (т — 1)-м шагах, не определяются командами программы (им даже нельзя присвоить номера по предложенному выше правилу, приходится нумеровать их отдельно, н они получают номера, большие чем номера команд, в правых частях которых они упоминаются).

Некоторая известная переменная г; равна значению сигнала о том, что найдено решение у(уь уь ..., у„) рассматриваемой массовой задачи перебора. Некоторые переменные г;, г„, ..., гх равны соответственно уь уь ... у — решению варианта задачи, который находит машина ИТ. Добавим к указанным выше уравнениям условие положительного результата процесса решения и допустимости выборов й«, (6=1, 2, ..., 1; 1=1, 2, ..., т — 1), состоящие в том, что для каждого номера шага 1 одна из переменных д«л равна 1, а остальные — О: ! «-1 ! Уо = гл = 1' У Ч« 1 = 1' ~/ '/ (Ч« а Ч« ) = О «=~ ' «,=««,=«,+~ (1 = 1, 2, ..., ч — 1).

Если полученная система имеет решение, то значения д«, (Й=!, 2,-, 1; 1=1, 2,..., т — 1) определяют ветвь процесса вычисления недетерминированной машины Тьюринга УТ, дающей положительный результат у«=в~ =1. Остальные результаты вычисления„в том числе допустимый ответ у,=ау, у,=г,м ..., у =г1, определяются через д«л однозначно.

В противном случае ни одна из ветвей не приводит к положительному результату, и если во всех них происходит остановка, то с отрицательным результатом. Пусть данная массовая задача перебора принадлежит классу 1УР, т. е. решается на некоторой недетерминированной машине Тьюринга МТ за 1(С«тс шагов, где т — информационная размерность варианта. Интерпретация произвольной ветви процесса вычисления машины УТ требует С;,1«=С' С'т'с элементарных логических операций, опре- 388 с ° 9 сс деляющих Согп ' = СоСот ' двоичных переменных аь К ннм надо добавить 1(1 — 1) переменных дьз(6=1, 2, ..., 1; 1=1, 2, ..., г — 1). Каждой переменной зз соответствует урав- нение системы, а переменной г; — еще одно: г; =1.

Пере- менным дад соответствуют 21 — 2 уравнений ~/ дал =- 1 В=1 и Ч . Ч (да,ада,'1 =О. Таким образом, чтобы найти ь, ~ ь,=а,+~ решение данного варианта х(хь хм ..., х ) массовой задачи перебора из класса КР, достаточно найти решение системы логических уравнений, в которой количества переменных с' с' с, с', Сот '+ 21 — 2=Сзт ' +1С,т ' — 1 < Со гп ' и уравнений Сот + 2Согп — 2 ~(Со т ограничены степенным обрас', с,' с,' зом (можно считать, что С" =С'+1Са). Если любую систему логических уравнений можно ре- шить на машине элементарных логических операций за вре- мя, степенным образом зависящее от количеств переменных и уравнений, то любая массовая задача перебора класса МР принадлежит классу Р, Действительно, по процессу решения задачи на недетерминированной машине Тьюринга Гг'Т, имеющему полиномиальную трудоемкость Г(Сзтс, с,' можно построить систему из Я~ <Сзт ' логических уравс", нений с Яз(Согп ' двоичными переменными, а затем ре шить ее на любой из рассматриваемых нами детерминиро- ванных машин (машине элементарных логических опера- ций, машине с произвольным доступом к памяти или до- статочно мощной машине Тьюринга Т) за время, степенным образом зависящее от Я, и 1,м и, значит, степенным обра зом только с большим показателем степени С'; — от т, Легко видеть, что массовая задача решения системы из логических уравнений с 1,ч двоичными переменными явля- ется массовой задачей перебора, так как длина ответа равна Ям т.

е, не больше описания варианта задачи. Она принадлежит классам РС и, значит, МР. Действительно, для вычисления предиката Р"'(х, у), равного 1, когда все Я, уравнений удовлетворяются, достаточно произвести ука. ванные в уравнениях элементарные логические операции и проверки равенств, т. е. число действий не больше, чем информационная раамерность системы гп — длина ее опи- сания.

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

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

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

У первых уравнений в левой части стоят какие-либо изолированные переменные, а в правой— другие такие же переменные, константы или элементарные логические операции, и условие положительного результата гг =1 имеет один из перечисленных выше видов (слева переменная, справа константа). Остальные уравнения можно привести к аналогичному виду, введя дополнительные переменные, но пе увеличивая существенно информационной размерности вариантов.

Действительно, эти уравнения имеют вид: ~/ дм; = 1; ~,Г '~ (г(х,лапь,;) =0 (1= 1,2,.„,! — 1). ь=~ ' а,=~ а,.—.а,+~ Они преобразуются следующим образом: "а, ~ Чзл и,, =п„,,ап„,(й = 2, 3, ..., ! — 1); и .=1; шь,л,л = 9мл а 9з,л! гал «л=О(й~ =1,2,...,! — 1, 6,=6,+1, ..., 1, ю' = 1, 2, ..., г — 1). В этих уравнениях столько же знаков й, сколько их в уравнениях, которые они заменяют; знаков ~/ меньше, и каждому уравнению со знаком соответствует не более одного уравнения без знака и не более одной переменной.

Общее число новых уравнений и неизвестных не больше, чем (1 — 1) (1+1+2((! — 1)+(! — 2)+...+!))=(г — 1) (Р+ +1) <Сг, т. е. степенным образом со степенью 1 зависит от сложности 1 варианта задачи относительно недетерминированной машины Тьюринга и степенным же образом с некоторой степенью С~ — от информационной размерности т варианта задачи. Итак, Л'Р-полной является задача решения системы уравнений, содержащих не менее трех переменных и имеющих один из видов: ~э=С;; ~,=~,а~; ь =Ь|Г1ь 1~.= ) 1~; Каждое из них эквивалентно таким логическим условиям: 1т=1» К'~l )Ыа( )1тЧЫ~ 39! ~т = ', 1а — Кз ~/ 1е) а ( 1 1т Ч ) 1~)б ~у =Ьа1ь ( ) 1г'/ 1а)а( ) 1т ~/ ~ )а(~т ~/ 1 ~ ~/ ) 1а)' ~г 1и" 1и — (1т'ч' ) 1ь)й(1~Ч ) ~и)й( ) 1г~/ 1ьЧ гь). Переменную, приравненную константе, можно в этих фор- мулах заменить константой; выражения вида ~;, '/ ~,~/...

" Ь,Ч1~1'/ ',1,',Ч".'/,~г; будем называть дизъюнктами. Каждое уравнение заменяется одним, двумя или тремя дизъюнктами, и все они должны выполняться; Поэтому рассматриваемая задача о решении системы логических уравнений эквивалентна задаче о выполнимости конъюик- тивной нормальной формы (КНФ) аз,.~,....с)-,'а (й~„), ь! где каждое $ь~ равно одной из переменных Ь» или ее отри- цанию ~ьм Требуется определить такие значения ьь ьв ... ...,1;, чтобы КНФ Фф, ~ь ..., ~ ) было равно 1, или дока- зать, что Ф(~ь ~ь ..., ь ) тождественно равно О. Следова- тельно, задача о выполнимости конъюнктивной нормальной формы тоже является ФР-полной.