1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 86
Текст из файла (страница 86)
Поскольку А и В утверждают, что в момент 1 головка обозре- вает только одну клетку и клетка с содержит лишь один символ, то в момент времени 1 либо головка обозревает клетку с, либо содержи- мое клетки с не меняется. Если раскрыть значение знака =, то длина Р будет 0(рз(а)).
5. Е утверждает, что очередное МО машины М получается из предыдущего одним переходом, разрешаемым функцией переходов б машины М. Пусть Есса, означает одно из следующих утверждений: (а) в момент 1 клетка с не содержит символа 1, (б) в момент 1 головка не обозревает клетку с', (в) в момент 1 машина М не находится в состоянии й, (г) очередное МО машины М получается из предыдущего переходом, разрешаемым функцией переходов машины М. Тогда П Есгы с, с. а, с где Ес хс — — — с С <1, 1, й> + ~ Н <1, 1> + з 8 <сс, 1>+ +~х~н~[С(с )о 1+ 1>Я(йп 1+ 1>Н(сс 1+1>) Здесь 1 пробегает по всем шагам машины М, возможным в случае, когда М обозревает символ Хс в состоянии с)„. Иными словами, для каждой тройки (с), Х, с(> из 6(с)со Х,) существует одно значение 1, для которого Хс,— — Х, дх,=с) и число с, равна с — 1, с или 1+! ч зависимости от с(: сдвигается ли головка влево (с(=Ь, 1,=с — )), с) х=-у означает ху+ху (х тогда н только тогда, когда у).
азз гл. )в ))г-полные з))д))чи вправо ()(=й, 1)=1+1) или остается на месте ()1=8, ),=1). Здесь 6 — функция переходов для М. Поскольку машина М недетерминированна, то таких троек (д, Х, )1) может быть несколько, ио во всяком случае их число конечно. Таким образом, Е))м имеет ограниченную длину, не зависящую отп. Поэтому Е имеетдлину0(р'(л)). б. Р утверждает, что выполнены начальные условия: АЙ=В<1, 0>Н<1, 0> П С<),1„0> Д С<1, 1,0>, 1<)<л и<)<р)п) где В<1, 0> утверждает, что М в момент 1=0 находится в состоянии д„которое мы считаем начальным; Н<1, О> утверждает, что М в момент 1=0 обозревает самую левую клетку ленты; Ц С<), 1„0> утверждает, что первые п клеток вначале )<)<л содержат входную цепочку пг, Д С<), 1, 0> утверждает, что л<)<р м) остальные клетки вначале пусты.
Мы считаем, что пустым символом является Х,. Очевидно, что Р имеет длину 0(р(п)). 7. 0 утверждает, что М в конце концов приходит в заключительное состояние. Поскольку мы потребовали, чтобы машина М оставалась в заключительном состоянии после того, как оно достигнуто, то 0=8<а, р(л)>. Мы считаем, что заключительным состоянием является Булева формула и), — зто произведение АВСОЕР0. Поскольку каждый из семи сомножителей состоит не более чем из 0(р'(а)) символов, сама формула ш,) также состоит не более чем из 0(р'(л)) символов. Так как мы считали каждую пропозициональиую переменную за один символ, а в действительности переменные представляются цепочками длины 0(!оя п), то на самом деле границей на 1п),~ будет 0(р'(и) 1од а), а это ие превосходит гпр'(л), где с — некоторая постоянная.
Таким образом, длина цепочки и), полиномиально зависит от длины цепочки ш. 1(олжно быть ясно, что если даны цепочка и) и полипом р, то формулу ш, можно записать за время, пропорциональное ее длине. По данной допускающей последовательности МО ()„ Я„..., 11 можно, очевидно, найти такое присваивание значений 0 и 1 пропозициональным переменным С<1, 1, 1>, 5<К 1> и НО, 1>, что и), примет значение истина. Обратно, если дано присваивание значений переменным формулы шм при котором она становится истинной, то легко найти допускающую последовательность МО.
Таким образом, формула и), выполнима тогда и только тогда, когда М допускает цепочку ш. Мы не наложили на язык Ь, допускаемый машиной М, никаких ограничений, кроме того, что он принадлежит классу 1)"У. Позтому мы показали, что любой язык из ФУ полиномиально трансформи- ю.ь нг-полнотл злдлчи выполнимости руем в задачу выполнимости булевых формул. Отсюда заключаем, что задача выполнимости ХР-полна. На самом деле мы доказали больше, чем утверждается в теореме 10,3. Говорят, что булеза формула находится в конъюнктивной нормальной форме (КНФ), если она представляет собой произведение сумм литералов, где каждый литерал имеет вид х или -тх для некоторой переменной х.
Например, (х,+х,)(х,+х,+х,) находится в КНФ, а х,х,+х, нет. Формула щ, построенная в доказательстве теоремы 10.3, практически находится в КНФ вЂ” ее можно представить в КНФ, увеличив длину не более чем в постоянное число раз. Следствие. Задача вьтолнимости булевых формул, находящихся в КНФ, МР-полна. Л о к а з а т ел ь с т в о. Лостаточно показать, что каждая из формул А,..., б, построенных в доказательстве теоремы 10.3, либо уже находится в КНФ, либо может быть преобразована в такую с помощью правил булевой алгебры, причем ее длина увеличится не более чем в постоянное число раз. Формула У, определенная равенством (10.1), уже находится в КНФ. Отсюда следует, что А, В н С тоже находятся в КНФ, Е и 0 тривиально находятся в КНФ, поскольку г и 0 — произведения литералов. Р— формула вида (х иу)+г.
Если раскрыть знак =, получится выражение ху+ ху+ г, (10,2) эквивалентное (х +у+а) (х+у+г). (10.3) Подставив (10.3) вместо всех вхождений (10.2) в Р, получим формулу, эквивалентную исходной, но находящуюся в НКФ и превосходящую исходную формулу по длине не более чем в 2 раза. Наконец, Š— произведение формул Е»м. Поскольку длины всех Е»м ограничены независимо от и, каждую формулу Е», можно преобразовать в формулу в КНФ, причем ее длина не будет зависеть от л.
Поэтому преобразование формулы Е в формулу в КНФ увеличивает ее длину не более чем в постоянное число раз. Итак, формулу в, можно представить в КНФ, увеличив ее длину не более чем в постоянное число раз. ( ) Мы только что показали, что задача выполнимости формул в КНФ 1чР-полна. Можно показать, что даже при более жестких ограничениях на вид формулы задача выполнимости булевых формул также НР-полна. Говорят, что формула находится в *к-конъюнктивной нормальнои форме (й-КНФ), если она представляет собой произведение сумм, состоящих не более чем из й литералов.
Задача к-выполнимости состоит в выяснении выполнимости формулы, нахо- ГЛ. РХ НР-ПОЛНЫЕ ЗАДАЧИ дящейся в й-КНФ. Для й=! и 2 известныдетерминированные алгоритмы полиномиальной сложности, проверяющие й-выполнимость. Ситуация (по-виднмому) изменяется при А=3, как видно нз следующей теоремы. Теорема 10.4. Задача 3-выполнииости ар-полно.
До к а з а т ел ь с т в о. Покажем, что выполнимость формул в КНФ полнномиально трансформируема в 3-выполнимость. В данном произведении сумм заменим каждую сумму (х,+х,+...+хл), й)4, на (х1+хз+у1) (хз+у~+уз) (х4+уз+ув) ...(х„,+У„,+у,,)(х„,+х„+УЗ,), (10.4) где У„у„..., УА,— новые переменные. Например, для й=4 выражение (10.4) принимает вид (х,+х,+У~)(хз+х4+У~). Присвоить значения новым переменным так, чтобы подставляемая формула приняла значение 1,можно тогда н только тогда, когда один из литералов х„ х„..., хл имеет значение 1, т. е.
тогда и только тогда, когда исходная формула принимает значение 1. Допустим, что х,=1, Тогда положим у~ — — 1 для 1(! — 2 и у!=О для !)! — 2. Подставляемая формула принимает значение 1. Обратно, допустим, что прн некоторых значениях переменных у~ подставляемая формула принимает значение 1.
Если У,=О, то одна из переменных х, и х, должна иметь значение 1. Если у,,=1, то одна из переменных хА, и х„должна иметь значение 1. Если у,=1 и УА,=О, то для некоторого 1, 1(!(й — 4, выполнены оба равенства у;=1 и у,+, ††О, откуда следует, что переменная х,„, должна иметь значение 1. В любом случае некоторая переменная х, должна иметь значение 1. Длина формулы, получаемой в результате описанной выше замены, превосходит длину исходной формулы не более чем в постоянное число раз. Таким образом, по данной формуле Е в КНФ можно найти, применяя описанное выше преобразование к каждой сумме, формулу Е' в З-КНФ, выполнимую тогда и только тогда, когда выполнима исходная формула.
Более того, легко показать, что Е' можно найти за время, пропорциональное длине формулы Е, выполняя преобразования очевидным образом. () 40.з. ЕЩЕ НЕСКОЛЬКО МР-ПОЛНЫХ ЗАДАЧ Теперь приступим к доказательству того, что каждая из задач, упомянутых в теореме 10.2, !ЧР-полна.
Для этого покажем, что в нее прямо или косвенно преобразуется выполнимость. Дерево на рис. 10.6 иллюстрирует последовательность преобразований, которые мы в действительности будем применять. Если Р— отец для 42$ |е.з. аща насколько нр.полных злдлч Рис. Ю.б. Последовательиость преобразований зля различных трудных задач. Р' на рис. 10.6, то мы покажем, что задача Р полиномиально транс- формируема в Р'. Теорема 10.5. Задача КНФ-выполнимости полиномиалько транс- формируема в задачу о клике. Поэтому задача о клика НР-полна.
Д о к а з а т е л ь с т в о. Пусть Р=Р,Р,...Ре — формула в КНФ, где Р, — сомножители; каждая формула Р, ймеет вид (хн+ +хм+, .+х;и), где хм — литерал. Построим неориентированный граф О=(У, Е), узлами которого служат пары целых чисел (1, 1) для 1(1(д и 1(1(йь Первая компонента такой пары представляет сомножитель, а вторая — литерал, входящий в него. Таким образом, каждый узел графа естественным образом соответствует конкретному вхождению в конкретный сомножитель. Ребрами графа О служат пары ((1, 1), (й, 1)), для которых з~й и хм~хан Неформально, узлы (1, 1) и [й, 1) смежны в О, если они соответствуют различным сомножителям и можно так присвоить значения переменным из литералов х» и хз„чтобы оба литерала приняли значения 1 (тем самым давая значение 1 формулам Р; и Р ).
Иными словами, либо хм=ха„либо переменные, входящие в литералы х» и х„„различны. Число узлов в О, очевидно, меньше длины формулы Р, а число ребер не превосходит квадрата числа узлов. Поэтому граф О можно закодировать в виде цепочки, длина которой ограничена полиномом от длины формулы Р, и, что еще важнее, такой код можно найти за время, ограниченное полиномом от длины Р. Мы покажем, что О содержит о-клику тогда и только тогда, когда формула Р выполнима. Отсюда будет следовать, что по данному алгоритму, решающему задачу о клике за полиномиально огранкченное время, можно по. гл. во, нг.полныа злдлчи строить алгоритм с полиномиально ограниченным временем работы для задачи КНФ-выполнимости, построив по Р графО, содержащий д-клику тогда и только тогда, когда формула Р выполнима.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
