Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 81
Текст из файла (страница 81)
Именно для таких задач выделен термин г?Р-трудносгль. Примером явтяется следующая задача. К-е ПО ВЕСУ ПОДй1НОЖЕСТВО Даны целые числа с„..., с„, К и Е. Спрашивается, существуют ли такие К Различных подмножеств Яь..., О„Ы !1„, л), что ~о»Е для! 1, ...,К. ! «зе !б.4. Словарь родственных ноняьнна 409 ь'(Другиыи словами, будет ли вес К-го по весу подмножества из ' (1,..., и) не меньше Е?) Входит ли задача К-е ПО ВЕСУ ПОДМНОЖЕСТВО в МР? Это совсем не ясно.
Какое удостоверение для индивидуальной задачи (с„..., с„, К, 1) с отвезоы да будет короче, чем выписывание всех К подмножеств, вес которых больше, чем Е? Естественно, этот вариант не будет коротким удостоверением, так как К может, напри' мер, быть равным 2" '. Тем не менее все задачи из МР полиномиальио сводятся (не преобразуются) к задаче К-е ПО ВЕСУ ПОДМНОЖЕСТВО. Теорема 16.8. Задача РАЗБИЕНИЕ полинольиально сводится к задаче К-е ЛО ВЕСУ ЛОДМИОЖЕСТВО. Доказательства Пусть у нас имеется подпрограмма А, решающая задачу К-е ПО ВЕСУ ПОДМНОЖЕСТВО Мы можем следующим образом использовать ее для решения произвольной индивидуальной задачи РАЗБИЕНИЕ с„..., со. !. Прежде всего определим порядковый номер )? в последовательности всех подмножеств множества,'1, ..., п) (упорядоченных по весу) самого легкого из подмножеств, вес которых не меньше, чем яно,с,!2. Естественно, если я'?,с, нечетно, то мы сразу же выдаем ответ нет.
Указанное)? определяем разряд за разрядом, п раз вызывая н(. 2 Если меньше чем 2" — )? подмножеств имеют вес, больший или равный ~", с,л2+ 1, то это означает, что по крайней мере одно (на самом деле по крайней мере два) подмножество имеет вес ~',с,?2, и поэтому мы выдаем ответ да.
В противном случае выдаем ответ неся. Е) Между прочим, это один из редких случаев, когда не известно, можно ли полиномиальную сводимость заменить более точным понятием полиномиального преобразования (вспомните предыдущий раздел). Термин МР-трудность используется в литературе не только для описания задач распознавания, про которые не известно, принадлежат ли они МР, но иногда и для описания задач оптимизации (которые, не будучи задачами распознавания, естественно, не при. надлежат МР), варианты распознавания которых МР-полны.
Например, можно сказать, что ЗК (т. е, задача оптимизации) МР- трудна. 16.4.3. Недетерминированные машины Тьюринга. МР— это сокращение от недетерхвинированневй полиножиальный (попде1егш(п)з11с ро!упош1а!). Оно связано с темечто исторически класс МР 4!О Гм <б. Еи<«об !«'Р-оолноо<е был впервые описан в терминах определенных вычислительных устройств, называемых недеа<ерл<инираванными машинами Тьюринга.
Машина Тьюрин<.а — это устройство, работающее аналогично алгоритму проверки удостоверения из предыдущей главы — отличие в том, что машина Тьюринга работает только на входе без удостоверения н имеет в своем распоряжении неограниченную ленту. Ее работа управляется программой с операторами вида й (1 а Феп(а'; о; Г). Машина Тьюринга принимает вход, если она достигает выделенного опера<ора й ассер1. Таким образом, класс Р можно определить как множество задач типа да-нет, распознаваемых машинами Тьюринга, причем с тем свойством, что вычисление всегда останавливается после некоторого числа шагов, ограниченного фиксированным поли- номом от размера входа.
Должно быть очевидным, что это определение совпадае< с нашим неформальным понятием лолиномиального алгоритма. Недеа<ермини!<аванная машина Тьюринга М представляет собой такое же устройство, гочько в данном случае программа содержит операторы более общего вида: 1; И а 1(<еп опе о( ((а,; о,, !;), (а,'; о,; (;), ..., (а„'; о<б !»)), При выполнении этого оператора М может выбрать любое одно из указанных я»! действий; отсюда происходит термин недетермини.
раоанная. Тогда класс !»'Р можно определить как класс всех задач А типа да-неш, для которых сущее<вуе< недетерминировалная машина Тьюринга М, такая, ч<о для каждой индивидуальной задачи х задачи А с ответом да существую последовательность допустимых «выборов» переходов мананы М, общая длина которой ограничена фиксированным лолиномом от (х), приводящая в заключение к оператору ассер1, и не существует таких выборов переходов для индивидуальных задач с отав<ам неви Докажем теперь, что это определение класса !»'Р эквивалентно нашел<у определению, в котором использовалось поня<не удостоверения. Прсдлоложим, ч<о для задачи имеется «короткое удостоверение». Тогда ее можно распознать на недетермннированной машине Тьюринга, которая вначале (недетерминированно) печатает после входа некоторое предполагаемое удостоверение подходящей длины, а затем моделирует применение алгоритма проверки удостоверения к построенной строке.
Поскольку наша задача обладает свойством короткого удостоверения, то для каждой индивидуальной задачи с ответом да существуеэ (и не существут ни для какой индивидуальной задачи е ответом нет) «корректное удостоверение», т. е. существует последовательность переходов недетерминированной машины, приводящая к оператору ассер1, и длина этой последовательное<и ограничена лолиномом, соответствующим данной задаче. !6.4. Слсварь радсгнвенных нонялшз 4!1 Обратно, пусть задачу А типа да-нвт можно распознать на не- -детерминированной машине Тьюринга с полиномиальной оценкой .Р(п). Тогда каждсе сосзояние этой машины при работе с входом длины и можно представить как слово из р(п) символов — многие из которых, возможно, пусты,— и определенной дополнительной информации, описывающей метку следующего выполняемого оператора и положение читающей и пишущей головки на ленте. Поэтому всю работу машины для индивидуальной задачи х задачи А с ответом да можно представить, выписывая подряд р((х!) таких слов с общей длиной 0(р'(1х1)).
Это описание работы машины можно проверить на правильность, убеждаясь, что каждое слово в ней получается нз пведыдущего одним из допустимых в этот момент переходов — а это требует всего лишь полнномнального времени. Следовательно, в задаче А все индивидуальные задачи с ответом да — и только они — имеют короткое н эффективно проверяемое удостоверение, а именно явную запись работы недетерминированной машины Тьюринга, которая оканчивается командой ассер(. Отсюда получаем, что определение класса й)Р в терминах недетерминированных машин Тьюринга эквивалентно нашему определению.
16А.4. Задачи, полные относительно полиномиальной памяти. У наг имеется класс Р задач, разрешимых за полнномиальное время, и класс 1н'Р задач, в которых индивидуальные задачи с ответом да имеют полиномиальное удостоверение. Если мы будем еще более великодушными н потребуем только, чтобы для задач существовали алгоритмы, использующие прн работе память, объем которой ограничен полиномом от размеров входа, то придем к классу задач, известному как Р$РАСЕ Если для работы алгоризма требуется только полнномиальное количество времени, он, очевидно, не можег использовать больше чем полиномнальный объем памяти, поэтому класс Р заведомо является подмножеством класса Р$РАСЕ. Класс НР также является подмножеством класса Р$РАСЕ. Чтобы понять это, представим себе машину, которая для данного входа систематически по очерели порождает всевозможные короткие улостоверения, стирая каждый раз предылущее удостоверение, и на каждом удостоверении моделирует работу алгоритма проверки удостоверения.
Эта машина работает экспоненциальпое время, гак кзк имеется огромное число возможных удостоверений подходящей длины, олнако она использует только полиномиальный обьем памяти. Такие же рассуждения показывают, что со-МРтР$РАСЕ. Прн этом класс Р$РАСЕ вполне может оказаться даже шире.
Например, обсуждавшаяся выше задача К-е ПО ВЕСУ ПОДМНОЖЕСТВО (принадлежность которой к М Р неясна) входит в Р$ РАСЕ. Это следует из того, что можно перебором просмотреть все подмножества множества (1,..., и), каждый раз стирая прелылущее подмножество и сохраняя в стороне количество (в двоичном представлении) уже просмотренных подмножеств, вес которых больше, чем Гл. !б. Еще об МР-иооооае 412 Е.
Все это можно проделать с использованием полиномиальной памяти. Задача называется РБРАСЕ-по.гной, если она принадлежит классу РБРАСЕ и все остальные задачи из класса РЯРАСЕ полиномиально сводятся к ней. Примером РБРАСЕ-полной задачи является вариант задачи ВЫПОЛНИМОСТЬ с кванторами, который мы ие будем здесь определять.
Для РЯРЛСЕ-полных задач принадлежность классу Р еще менее вероягна, чем для УР-полных задач, так как класс РБРЛСЕ Рис. 16.5, содержит класс 1хР (и, следовательно, из равенства Р=РБРЛСЕ вьпекало бы Р— КР). В свете этих новых понятий мы можем получить окончазельный предполагаемый вид класса АР и его окрестности, приведенный на рис. 16.5. На очень слабое понимание нами этой области указывает тот факт, что, несмотря на все, что мы знаем, вполне возможно, что все эти области могут слиться в одну: Р1 16Л Эпилог Нельзя сказать последнего слова о труднорешаемости 1е Р- полных задач да тех пор, пока не будет разрешена гипотеза Р Ф ХР.
Несмотря на большую зеоретическую важность этой задачи и высказываемый интерес к ней многих специалистов по вычислительным наукам, доказательства этой гипогезы пока не видно. В настоящее время кажется вполне вероятным, что отвез на этот вопрос не удастся получить без развития совершенно новых математических методов. При формировании небольшого списка задач, Л/Р-полногу ко1о. »»Х Эпилог 413 г ' рых мы доказали в предыдущей главе, мы выбирали только те зада, чи, которые относятся к комбинаторной оптимизации илз достаточно , фундаментальны и полезны в качестве отправных пгчек для доказа'тельства МР-полноты других задач Однако имее ся еще много й(Р-полных задач, появляющихся в разнообразных дисциплинах, таких, как зеория графов, оптимизация, математическое программи- рование, логика, теория чисел и зеория вычислений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
