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

УР-полна и обратная задача о тождественной истинности дизъюнктивной нор- мальной формы: / "~ Система логических уравнений эквивалентна системе линейных уравнений для булевых переменных, т.е. двоич- ных переменных, рассматриваемых как целые числа, при- чем информационные размерности соответствующих вари- антов по порядку — те же. Добавить переменные ц~= (1=1, 2,..., и) и переменные дь,, соответствующие некото- рым логическим уравнениям. Уравнение ~~= С; можно с одинаковым основанием считать либо логическим (С; равно О или 1), либо линейным; переменные ~~ и т1; связаны условиями ~;+ту=1 (1=1, 2, ..., и).

Уравнения ~;=~а и ь;= ~ьь=ць можно заменить эквива- летными линейными уравнениями ~;+Ч,=1; ~,+~а=1, уравнения ~;=~ьй~л — сначала неравенствами ьг> 1Ф 11> ьл 1А+~ > ь/ затем неравенствами ~т + Чь > 1' ~~ + ць > 1; 1а+ 1ь + Чг > 1 392 и, наконец, равенствами ь,+Ч +бш=2; ь';+П.+О; =2; ь +ь,+Ч,+ +б,„+бе„=з, Действительно, если ~~+т1д~1, то при некотором значении булевой переменной дьь где 1 — номер рассматриваемого логического уравнения в исходной системе логических уравнений, Ь,+т1ь+Ос~=2: если ~;-1, пь=1, то Ош= =О, если ь,=1, их=О, то д,я=1, а других зйаченнй эта сумма иметь не может.

Аналогичным образом заменяется неравенство ~;+т1х» 1. Сумма Ьх+~ь+тп может быть равна 1, 2 или 3. Соответственно д;л=дс4=1, доз=! н дс4=0 (или 6;а=О, Оь4=1) или дсз=бь4=0. Наконец, логическое уравнение ~,=Ьь~/~з можно заменить эквивалентным т1~= =' ~~з= )(~ь~/~л)=)~хй )ьл=т1хйци, а последнее — равенствами; Ч, + ~а+ б,л = 2' Ч; + ~а + О~ з = 2' ЧФ + Чь + 1' + 6' 3 + б' 4 3' Таким образом, задача решения системы линейных уравнений для булевых переменных Л'Р-полна (легко показать, что она принадлежит классу РС и, значит, классу МР). Следовательно, МР-полна многомерная задача о камнях, частным случаем которой она является. Покажем теперь, что МР-полна и одномерная аадача о камнях л ~ Ь~ ~~ = М; ~~ Я (О, 1) () = 1, 2, .„, и), г ! Переименуем все переменные в МР-полной задаче о решении системы линейных уравнений с булевыми переменными, эквивалентной системе логических уравнений.

Тогда она будет иметь вид л ~~у~ацсРЗ =- Ь;(1 = 1, 2, ..., М = 2п+ 41), /сн где и — число переменных ьь ьм „., ь„, а 1 — число уравнений в исходной системе логических уравнений; все коэффициенты а;; равны 0 или 1, причем количество равных 1 коэффициентов в каждом уравнении не больше 5, а их правые части равны О, 1, 2 или 3. Рассмотрим задачу 393 о камнях ')'А;!р! — — В, /=! л !т где А!=~ч~ап 6! ' (1=1, 2,.„, и); В=~РЬ; б' ', и докажем, ! ! с=! что она эквивалентна системе линейных уравнений с булевыми переменными и имеет такую же по порядку информационную размерность т'. Введем обозначения: л и А ~~ аы б!-! А! 6 ~~~Р а! 6!-! + а т 6А! + а Е=2 6'! =6 ~ а!!б + !=!ы-! (! =2,3,...,Л' — 1,1=1,2, ...,и); 6 ~Р Ьт 6' +Ь! — В,=6В,+Ь;, В! = чпЬ, 6! ! =6 ~~~~ ~Ь! б! ! +Ьа = =6Ва+, +Ьк((=2,3, ..., Л! — 1); А~!+'=Влч.!=0 (!=1,2, ...,п), Пусть рассматрпваемая задача о камнях имеет решение !р!, !рэ, -, (р4 Тогда '~~~ А !р; = ~~~~ !'=.! /=! и + ~~~ аы !р! = 0~( ~~~~ аы!рт(б; !=! 0<Ь <б; У А!' ~~Р а! ! е! + аа! == 6А! + а!; В = '~Ь,"6'='= !=! А,'гр; = 6 ~~ А!!р;+ у=.! В =В =6В,+Ь;, 6 ~~«~А;гр/ делится на 6; /-! 6В, делится на 6.

Следовательно, И л ~~~~ ~ам р/ = Ь„~ А/ /р = В,. !=! /=! Аналогичным образом доказывается, что '«~ ~а;/ !р! = Ь/ (1 = 2, 3, ..., У). / ! Если же /р!, !рм ..., /р„— решение системы линейных уравнений и а!/ =- Ь! (! = 1, 2, ..., /1/), то /=! Л // л и ~~' А/!р/ = ~ 6' ' ~~~ а;/!р/ — — '~~ 6' 'Ь! =В. !=! !=1 /=! !=-! Таким образом, доказана эквивалентность рассматриваемых задач. При самом коротком описании системы линейных уравнений нужно воспользоваться тем, что в каждом уравнении не более пяти коэффициентов ап равны 1, а остальные равны О. Значит, достаточно указать номера коэффициентов, отличных от О. Эти номера ие меньше 1 н не больше и.

Для их описания в двоичной позиционной системе достаточно / 1одз и 1' символов на каждый, а всего — не больше 51 !оц2 и ~. Однако, так как нужны еще разделители, то либо в алфавите должны быть символы, отличные от 0 и 1, либо цифры в изображении номеров /, для которых ап 1, в двоичной позиционной системе придется изображать парами символов, например, вместо 0 писать ОО, а вместо 1— 01. Итак, для описания коэффициентов матрицы !!а!/!! достаточно /!/~ 1оп2и ) символов алфавита (О, 1). На каждую правую часть, равную 1, 2 или 3 (в двоичной позиционной системе 01, 10 или 11), достаточно двух символов.

Значит, размерность задачи о булевых решениях системы линейных уравнений и! -~ с (/(/ ! 1оя, и ~ + 2и) ~~ с' Л/ ! 1ояз и ~. 395 Каждая переменная исходной системы логических уравнений один раз входит в правую часть, кроме переменных г;, ол,~ и жь,.л„которые входят в правые части двух уравнений (правда, в одном из них они приравниваются некоторым константам, но для простоты мы не станем этого учитывать; все равно порядок размерности вариантов не изменится). Значит, количество уравнений в системе равно с"и', где и' — количество неизвестных и 1~с" (2. При переходе к системе линейных уравнений увеличиваются количества переменных и уравнений: добавляются переменные П;= )~; (их л' штук) и не более четырех переменных Осл на каждую исходную переменную. Таким образом, количество переменных и пе меньше, чем 2л', и не больше, чем 2п'+4с"и'=с'"и', т.

е. имеет тот же порядок, что и и'. Каждому уравнению системы логических уравнений соответствует не менее одного и не более четырех уравнений системы линейных уравнений, Значит, количество последних Л~ не меньше, чем с'и', и не больше 4с'л'. Поэтому И=сп, где с")с"'<с~2с" и т -.с'сп ( 1од~ и 1. Коэффициенты А;(/=1, 2, ..., л) и правая часть В задачи о камнях — целые числа, не превосходящие бм. Для их изображении в данной позиционной системе нужно У~ 1оцз 6 / двоичных символов на каждое число, с учетом необходимости разделительных знаков — всего сЛп~сслз( ~стз.

Поэтому алгоритм решения одномерной задачи о камнях, имеющий полиномиальную сложность степени Сь относительно некоторой детерминированной машины, может быть применен для решения системы логических уравнений, причем его сложность не будет превосходить С'. Л'Р-полнота одномерной задачи о камнях доказана. В последнее время была доказана Л'Р-полнота очень многих задач, имеющих прикладное значение. Мы еще остановимся только на доказательстве Л'Р-полноты задачи о покрытии множества системой подмножеств. Рассмотрим исходную систему логических уравнений (с добавленными переменными па,~ и юмл,) и произведем следующие преобразования. 1. Добавим переменные тн= ~ьь 2.

Исключим переменные ~ь если в систему входит уравнение ~; сь и, естественно, исключим это уравнение. В других уравнениях заменим такие переменные соответствующими константами. 396 3. Произведем замены переменных.п исключения урав- нений, соответствующих уравнениям ~,=~а и ~~= 1ьа Чм исключив переменные с ббльшими номерами. 4. В результате таких преобразований останутся урав- нения следующих видов; ь7=$ааЬ; 1=9ааЬ ~7=$з''9и', О=1! аЬь; Ьз=-5„аО=О; 1=$„','йа, 1~=-заа1=$з' О=за'/$ь' Ь7 ьзаЧз 1 Чз 1 ~7 -1 г, 17 = $» ~/ О = $а,' 1,=т,~/1= 1; = "-з '/ Чь = 1~ где 5л — это либо Ьа, либо Чм Некоторые из этих уравнений дают возможность исключить переменные, применяя преобразования 2 и 3; уравнение ~~=3ьйО равносильно уравнению ~;=О; ~~=~а хт1а тоже равносильно уравнению Ьг О; ~~=$зй 1 равносильно уравнению М =~и, '4~=$а~/Π— такому же уравнению, ~;=$а\/1 и ~~=~а~/Чз равносильны уравнениям ь;=1; из уравнения 1=Кзй $з следует, что аз=1 и $з=1, а из уравнения 0=$ь~/$ь — что ьь=О и 9» =О.

Процесс исключения переменных продолжается, пока имеется возможность. Можно показать, что он имеет степенную трудоемкость относительно информационной размерности т исходной системы логических уравнений. Действительно, каждый цикл просмотра уравнений и исключения некоторых из них имеет трудоемкость 0(У), где У вЂ” число не исключенных к данному моменту уравнений; число таких циклов не больше Уа — начального числа уравнений. Таким образом, общее число действий 0(Л",)(0(гп'), где т — информационная размерность исходной задачи. В начале исключения переменных Жз(2гп, значит, и в конце его У(2т. Процесс может закончиться исключением всех переменных. Тогда их значения определяются, т.

е. задача будет решена. Однако в большинстве случаев количество оставшихся уравнений и переменных будет иметь такой же порядок, что и до исключения. В результате нужно будет решить систему, состоящую нз уравнений вида 397 1т = ьл Ь ь»' 1 = ь» '/ »»! 9!= 3»~/9»; %= (ьп 0 = 5»85,; Их можно заменить системой неравенств. Вместо =$»х9«, как и выше, рассмотрим неравенства $»+~1,)1; $»+тн)1; тп+ 1$«+ 3»)1, вместо ~9=5»~/$~ — неравенства 1й»+~~))1; 1$»+~;))1, и ~~~+в»+9»)1, '0=3»й$» равносильно неравенству ~9»+ 1$»)1; 1=$»'/$» — неравенству 5»+$»)1, и только условия Ч;= ~ (~ эквивалентны равенствам ~~+~(~ 1.

Перенумеруем оставшиеся переменные ~~ и ~!ь их будет одинаковое количество п'(п, где п — число переменных в исходной системе уравнений, имеющее тот же порядок, что и число уравнений и информационная размерность и. Равенства Ьу+~(;=! можно заменить неравенствами ~~+ л' +пн)1 и одним равенством », (~;+й>) =и'. Каждому не/=! равенству полученной системы поставим в соответствие точку п~ некоторого конечного множества У, а каждой переменной Г; или кн — подмножество В',. или Я7;.

соответственно, состоящее из точек пь для которых 1-е неравенсФ- во содержит эту переменную. Легко видеть, что наша система равносильна задаче о покрытии множества к' системой из п' подмножеств, часть которых — некоторые 1Р, а ос/' тальные — некоторые (р':. Значит, и задача о покрытии л УР-полна. Некоторые итоги. Проведенные нами исследования показывают, что искомым инвариантом теории трудоемкости вычислений является понятие полиномиальной трудоемкости, Переход от одной машины к другой изменяет трудоемкость задачи полиномиальным образом; поэтому, если задача имеет полиномиальную трудоемкость вычисления, то это ее свойство не зависит от выбора машины.