Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 79
Текст из файла (страница 79)
е. с трудоемкостью, не превосходящей Сопл 'и!*и!', где Со, С!, Съ Сз — конс, с, с, станты (свои для каждой задачи). Классу Р принадлежат задачи определения следующего натурального числа х+1, суммы у=х!+хз, произведения у=х,хз и т.д. К ним относится и задача РЕлтТ. Только за- дачи класса Р можно считать эффективно решаемыми, да и то при условии, что показатели степени С!, Сз, Сз не слишком велики.
Задача принадлежит к л а с с у РС (классу задач с по- лииомиальной трудоемкостью проверки), если ее преднкат Р'"' " " (х, у) (или Р" (х, у)) вычисляется на некоторой машине Тьюринга с полиномиальной трудоемкостью. За- дачи о камнях, о покрытии множества подмножествами, о выполнимости конъюнктивной нормальной формы, вооб- ще об определении значений двоичных переменных уьуз, ... ..., у, удовлетворяющих условиям л ~~' х! у!= М! (! = 1, 2, ..., 1), !=1 относятся к этому классу. 381 Действительно, проверка выполнения условий требует Й(п+1) арифметических операций, а арифметические — не более чем 8т логических, где т — сумма длин всех чисел х' иМ.
Естественно, задачи класса Р являются также задачами класса РС, но существуют ли задачи класса РС, не принадлежащие классу Р, пока не известно. Мы еще вернемся к этому вопросу. Отметим в соответствии с результатами, полученными в $9.1, если задача решается с полиномиальной трудоемкостью на машине одного класса, она решается с полиномиальной трудоемкостью и па машине другого класса. Поэтому принадлежность задачи классу Р или РС не зависит от выбора машины, для которой оценивалась трудоемкость вычисления этой задачи; иначе говоря, классы Р и РС инвариантны относительно выбора детерминированных машин. Другой подход к классификации задач по сложности основан на понятии недетерминироваиной машины Тьюринга.
Недетерминированная машина Тьюринга моделирует алгоритмы с некоторой «свободой выбора», причем нас интересует, сколько времени понадобится, если с выбором «всегда будет везти». По крайней мере некоторые команды недетерминированной машины Тьюринга НТ при одной и той же истории ее работы и, значит, при одном и том же ее полном состоянии могут выполняться разными способами. Для каждого внутреннего состояния машины и читаемого с ленты символа эти способы заданы. У машины Тьюринга КТ также имеется конечный набор внутренних состояний (з1,);=ь и алфавит символов на ленте (зут,) (1'-1, 2.....т) тоже конечен. Однако правила действий имеют внд списков: з1, зупь тоое; л к' зт, аут. тоое„; ь 1» ьв 81~ зут -1. з1 й зут,, глооеео где 1 — это максимальное число вариантов выполнения действия.
Если для некоторых внутренних состояний зй и читаемых символов аут~ вариантов меньше, то последний будем дублировать так, чтобы их стало 1. Перед выполнением очередного действия из одной ма- шины возникает 1 машин. Записи на их лентах олив»козы — такие, какие были у их «предка», но с этого момен~а нх пути расходятся: каждая машина выполняет свой вариант действия из списка. Процесс работы детерминированной машины Тьюринга Т (и любой рассмотренной раньше машины) может быть изображен в виде линейной последовательности действий, а процесс работы недетерминированной машины УТ вЂ” в виде дерева, вершинами которого являются выполняемые действия, а ребрами — переходы от одного действия к следующим (рис. 9.2).
Таким обра- 1 ~-":я зом, она одновременно решает задачу разными способами, чтобы не упустить тот, при котором «везет». Каждый способ — это последовательность машинных операций, которой соответствует цепь дерева работы машины ИТ с началом Рис 92 в корне. Если по некоторой цепи действия заканчиваются, то возможны два исхода: задача решена или решение не найдено. В первом случае все остальные машины, размножившиеся к этому моменту, тоже кончают работу и преврашаются в одну машину. Во втором — они продолжают работать. Если же по всем цепям произойдет окончание вычислений с отрицательными результатами, то все машины тоже сливаются в одну: задача не имеет решения. Других обменов информацией между различными вариантами процесса работы машины не происходит.
Класс МР. Что значит решить данную массовую задачу перебора при значениях параметров размерностей и, и,, и» или только глг Каждому варианту х(х„хь ..., х„) такой задачи надо уметь поставить в соответствие ответ у(уо, пь ...,у ). Если у«=1, то вариант имеет решение, и значения уь ум ..., у — это описание некоторого из них (решение может быть не единственным). Если у»=0, то задача не имеет решения, и значения по ум ..., у могут быть какими угодно. В дальнейшем будем предпочагать,что учитывается только информационная размерность и. Пусть имеется не- детерминированная машина Тьюринга ИТ, которая при любом варианте' х данной массовой задачи не позднее чем через С, тс шагов останавливается и дает ответ, положительный (д0=1) или отрицательный (да=О), причем Со и С, — константы.
Тогда рассматриваемая задача принадлежит классу ИР. Так как обычную машину Тьюринга Т можно считать частным случаем недетерминированной с количеством разветвлений 1= 1, все задачи класса Р являются задачами класса йГР. Теорема 9.4. Все задачи класса РС принадлежат классу ИР, Д о к а з а т ел ь с т в о. Пусть машина Тьюринга Т не более чем за Сатс шагов вычисляет предикат до=Р~(хо хм -., х,, дь дм -., д.,), т. е.
проверяет, является ли набор переменных д(дь дм ..., д ) решением данного варианта х(хь х,, ..., х ) массовой задачи перебора, причем читающая и пишущая головка должна находиться над левой ячейкой информативной части ленты, а запись на послед- . ней имеет вид, приведенный на рис. 9.3. Сначала идет опи- ч Л д Иврормачия Рис. 9.8 саине задачи, заканчивающееся знаком конца, например, ".". Затем идут значения х„х,, ..., х, снова "." д~ дз ...
// // э ь м ...,д, и последний раз ., на чем информативная часть ленты кончается. На ленте недетерминированной машины Тьюринга 1т Т в начале работы находится такая же запись, причем д~ —— =д,=...=д =О. У нее есть переходы в новое состояние с порождением двух ветвей и переходы без разветвления (формально 1=2, переходами без разветвления мы считаем переходы, если внутренние состояния, символы, которые пишутся в ячейку ленты, и движения читающей и пишущей головки на обеих ветвях одинаковы). Начальное внутреннее состояние з(„р (пройти описание задачи) определяется строками таблицы переходов: > з(р КЮ Рй Здесь )т'М7 означает — не записывать нового символа в ячейку, а оставить тот, который был. Следующее состояние Ир„(пройти описание варианта) тоже не производит ветвления: з|„„).— я1„„ИУТь; а|„, -+-М „УВ'ЯЬ. Теперь происходит порождение всех вариантов ответов У~ Ух " Уп,: )М,„ОЯй; (Ф „1)сй.
В течение т шагов машина ЖТ читает на ленте символы О, и в одной ветви оставляют его без изменения, а в другой заменяют на 1. После этого возникнут экземпляры машины МТ со всеми вариантами ответа ОО...00, ОО...Ю~,ОО...Ю,...,П...~~. ~ нм Наконец будет прочтен символ '." И „) О-м1 )Ч)РЩ. Во всех ветвях, отличающихся друг от друга виртуальными ответами д= (дь ум ..., У„), надо вернуться к началу информативной части ленты. Предполагается, что внутри нее нет символов пробела Х. Тогда годятся переходы а|, )Ь +з( ИФЦ; а1п)~-+ аГгМ™М Пишущие н читающие головки всех экземпляров машины ИТ оказываются над начальными ячейками информативных частей лент, после чего эти машины начинают работать, как машина Тьюринга Т, т.
е. вычисляют значения предиката УО=Р"'(хь хм ..., х, уь дм.-, у ) при всех допустимых значениях у(дь ум ..., у ). Для этого машина ИТ имеет внутренние состояния, аналогичные состояниям машины Т: у них такие же таблицы переходов (одинаковые на обеих ветвях). В частности, состояние Ит, в котором находятся все экземпляры машины 1т'Т в рассматриваемый момент, аналогично начальному состоянию машины Тьюринга Т. Если данный вариант х(хь хм ..., х ) массовой задачи имеет хотя бы одно ре- 25 — 750 385 шение, то не позднее чем через Со а!с шагов после предварительной работы некоторые экземпляры машины МТ вычислйт До=Р~(х1, хго..., хт, Д1, Цм..., Рт), остановнтса и дадут положительный сигнал.
Работа остальных экземпляров прекратится. В противном случае, тоже не позднее чем через Сота шагов, от всех экземпляров машины 11~Т будут приняты отрицательные сигналы, все они остановятся, т. е, будет обнаружено, что вариант х(х1, хм ..., х ) не имеет допустимого решения. Остается оценить количество шагов предварительной работы, т. е. порождения вариантов. Читающие и пишущие головки всех экземпляров машины УТ сначала проходят над всеми ячейками информативной части ленты слева направо, затем — справа налево, делают еще шаг влево и шаг вправо и переходят к вычислениям предикатов уо=Р~(х, у).
Таким образом„на порождение вариантов уходит А— — 1+1.+1=21 шагов, где Ь вЂ” длина информативной части ленты машины 1о'Т (и Т) в начале вычисления. Эта часть состоит из постоянного количества ячеек, не зависящих от варианта и предполагаемого ответа, и (2т+2) ячеек, ЗаНЯтЫХ ОПИСаНИЕМ Х(Х1, Хто ..., Х ) И У(д1, УО, ..., У* ), ЕСЛИ считать символы концов описания — '.'. Значит, полное количество шагов не больше, чем 21+Со тс =2(сопз(+ с, ° с,' +2а!+2) +Со а! !(Со!и ! при Со = Со+2 сопя(+8, С! =щах (С„1). Оио полиномиальным образом зависит от размерности варианта задачи, (3 Интерпретация ветви процесса вычисления недетерминированной машины Тьюринга 1о'Т элементарными логическими операциями отличается от интерпретации процесса вычисления детерминированной машины Тьюринга только макрооператорами соа!р(!): вместо з!!'л= '/ '/ Тай, озз!р аз!!и г (1 =-1, 2, ..., а); 1=! о ! зр!и !а!1= ~/ 1,' Тай! „,. аз1р,а зут г (! = 1, 2...
т); /=1 1=1 тоаа! ! = ~/ '/ Таб! „„,, о а з!р х зуа! г„(! = — 1, О, 1) /=1 1=! надо вычислить о го з(!1:= '!!' ~/ '/ Тай!лм, эзар азут г дд„(! = 1, 2,, а); 1-1 1=1 Ь=! П гП зУп! ц!!' = ! ! ~l 'I у ой!+,.! ! ь ь~ згр а зУл! гьа!)л(!=1~ 2 "° пт)~ /=-! /г=! а=! и ю лоза!: = '/ ',l ~/ Таб! „, +, ааЫР изут г а!т„ ! ь=! ь=! (!= — 1,0, 1). Здесь и — количество внутренних состояний экземпляра машины; т — число символов алфавита, которые могут быть записаны в ячейках лент; 1 — количество разветвлений при выполнении шага недетерминированной машины Тьюринга ЛгТ. Однако имеется принципиальное различие: при интерпретации детерминированной машины Тьюринга результаты предопределены, так как каждая операция либо производится с ранее вычисленными переменными, либо состоит в присвоении некоторой переменной значения 0 или 1, записанного в команде машины элементарных логических операций; при интерпретации недетерминированной машины то же можно сказать обо всех переменных, кроме дь(1!=1, 2, ..., 1), которые на каждом шаге определяются выбором ветви.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
