Н.М. Новикова - Дискретные и непрерывные задачи оптимизации, страница 2

Лля ряда других задач удается доказать их ыеполиыомиальыость. Так, известны 1) алгоритмически ыеразрешимые задачи, когда ие существует алгоритма, решающего любую иыдивидуальыую задачу, т.е. УА 31 б П: А ые применим к 1, в частности, Фл(с(1)) = оо; например, 10-я проблема Гильберта: по данному мыогочлеыу у с целыми коэффициентами выяснить, имеет ли уравнение у = 0 целочисленное решение (неразрешимость доказал Ю. М. Матиясевич в 1970 г.); 2) задачи (не являющиеся задачамн распознавания свойств), для которых длина записи решения превосходит любой наперед заданный полипом от длины входа, например в задаче кОммивояжера, если требуется найти все маршруты (их зкспоненциальное число); 3) в остальных случаях формально имеем УА, решающего П с кодировкой е, Ур(.) Э1 б П: 1л(е(1)) > р(/е(1)~).

Здесь и далее р( ), возможно с индексами, служит для обозначения полиномов. В настоящее время для любой массовой задачи П, для которой доказано последнее условие, получен и более сильный результат: отсутствие полиномиального алгоритма, использующего произвольное (пусть бесконечное) число параллельных процессоров. Вопрос, существуют ли неполиномиальные задачи П распознавания свойств, которые оказываются полиномиально разрешимыми при возможности распараллеливания вычислений, является основной методологической проблемой теории сложности (обусловившей ее формирование как самостоятельной научной дисциплины). Ответ, по-видимому, должен быть положительным, и уже указан большой класс массовых задач в качестве кандидатов (см.

класс ХРС в $2), но доказать или опровергнуть зту гипотезу в данный момент представляется нереальным. Для ее формализации вводится объемлющий Р класс нвдеглерминирооанно полиномиальныя задан — ХР. 3. Определим недешерминироаанную машину Тьюринга (НДМТ) А как набор обычных — детерминированных — машин Тьюринга (ДМТ) А(5) с алфавитом Е, где Я пробегает все множество слов из А =' (А(Я))аех..

НДМТ А останавливается, когда останавливается первая из ДМТ А(Я), принимающая входное слово. Соответствующим конечным состоянием будет ау. Яэын НДо1Т вЂ” множество слов, прннимаемых хотя бы одной ДМТ А(5) из А: А(А) = (и б Е'~ ЗЯ б Е*: о б ЦА(Я))). Слова Я в определении НДМТ можно проинтерпретировать как подсказки к решению (догадки), тогда ДМТ А(Я) проверяет для входного слова вг подсказку Я и в случае правильности останавливается в состоянии ег. НДМТ А проверяет для входною слова е все возможные подсказки, и если хоть одна правильная догадка сушествует, то НДМТ останавливается с ответом "да".

(В силу бесконечности числа догадок, в состоянии в)н НДМТ остановиться не может.) ОПРЕДЕЛЕНИЕ 3. НДМТ А решает массовую задачу П с кодировкой е, если Ь(П,е) = Ь(А), т.е. языки НДМТ и задачи совпадают: )ввг й ЦП,е) ЗЯ б Е': ДМТ А(Я) останавливается в состоянии ет, и %г б Е' ) ЦП,е), УЯ б Е' ДМТ А(Я) не принимает е (не останавливается или останавливается в состоянии дн).

Определим Че Е ь(А) ерелл работы НДМТ А над словом е как минимальное из времен работы над входом е ДМТ А(Я), принимающих з, с учетом времени прочтения слова Я (т.е. его длины): Хв(е) =' ппп (Д + 4л(з)(вг)). (з~ ееьлвзв) Временной с*ежностмо НДМТ А решения массовой задачи П назовем функцию Тв ( ): Ул б Е+ ТА(п) = ивах ФА(е) = ивах ппп (ф~+вл(з)(вг)). ея)(А): (н(<н еей(А): (а(<н (З(еяснвзВ) Подчеркнем разницу с определением временнбй сложности ДМТ: для НДМТ рассматриваются лишь слова из языка (соответствуюшие индивидуальным задачам с ответом "ла"). ОПРЕДЕЛЕНИЕ 4, Клесс недетерзвинироеенне нолиномнельныя задав )в)Р =' ЩП,е)~ ЭА — НДМТ, решаюшая П с кодировкой е, Зр() — полипом: ТА(н) < р(н) Чн б Е+). Если для задачи П существует такая кодировка е, что ЦП,е) б )в)Р, то будем называть задачу П недетерзвиннрееанно волнномаельноя и пользоваться обозначением Пб)в)Р (кав( и для класса Р, корректным).

Примером недетерминированно полиномиальной задачи является КМ, ибо в качестве догадки можно использовать маршрут и проверка его дсвпустимости полиномиальна. Отметим, что полиномиальность проверки гарантируется только для индивидуальных задач с ответом "да" (и возможно, лишь при единственной подсказке), а для 1 б Р(П) 1'1т(П) НЛМТ просто не остановится. В этом — существенное отличие классов Р и ХР.

Непосредственно из опрелелений следует Утвегждение 1. Р с ХР. Вопрос о наличии строгого включения и является формализацией основной проблемы теории сложности. з2. ИР-полные (универсальные) задачи Теорема оо экспоненциальной оценке еременпдй слозсностпи дея задвч из класса ХР. Класс со-«1Р. Задачи, имеющие хороитую характперизацию. Определение полнкомнвльной сеодимосши.

К«асс ХРС. Теорема Кука (йез докаэатпельстпва). Критпернй 1чР- полнотпы. Доказан«ельстпво «1Р-полнотпы задачи БЛН (булевы ликейкые керавенсптвв). 1. Рассмотрим подробнее класс ХР. ТБОРЕМА 1. Лля любой недетерминированно полиномиальной задачи существует ЛМТ, решающая ее с экспоненциальной временной сложностью, т.е. УПб1чР Зр( ) — пслином — и ЛМТ А: А решает П и Та(п) < 2э1"1 уп б Еь.

Локязлтнльство. Так как ПбХР, то для любого слова «т из языка задачи П существует правильная догадка Я полиномиальной длины: ~Я~ < р«Оо~), р«() — полипом, и существует ЛМТ А(Я): 1ь1з1(«т) < рз()«т~)> рз(.) — полипом. Построим ЛМТ А, которел работает над любым входным словом «т б Е' (с любой индивидуальной задачей 1 б П) следующим образом: рассматриваются все слова Я из Е' длины меньше рт(~о~) и делается не более рз(то~) шагов с каждой ЛМТ А(Я). Если очередная ЛМТ останавливается в состоянии оу (т.е.

соответствующая догадка оказалась правильной), считаем слово о принятым и работу ЛМТ А законченной; если ни одна из ЛМТ А(Я) не остановилась за отведенное время или остановилась в состоянии ук> то заканчиваем работу ДМТ А и приписываем ей конечное состояние фг. В последнем случае ЛМТ А делает наибольшее число шагов, и это число меньше рзооО. ~Е)э>1«о«1 (второй сомножитель равен числу проверяемых догадок, ~Е~ — число символов в алфавите Е). Отсюда уя«е нетрудно получить утверждение теоремы. 10 Для того чтобы лучше почувствовать различие классов Р и Р1Р, введем понятие допеляиязсльиоя в П массовой задачи' П, получающейся из П распознавания свойств заменой альтернативного вопроса, определяющего ответ в задаче (см. п.2 'определения П в з1) его отрицанием, например вопросом в КМ "правда ли, что не существует маршрута длины, не превосходящей В?". Формально 1У(П) = П(П), Х(П) = 1з(П) ~ Х(П).

Определим классы дополнительных задач со-Р =' (П~ П б Р) и со-ЯР =' (П~ П б г1Р). Из определений очевидно, что если ДМТ А решает П, то 11МТ А решает П, где программа ДМТ А получена из прогррммы Д1ИТ А простой заменой конечных состояний дг и цл друг на друга. Таким образом, справедливо Утвегждкнив 2. со-Р = Р. Аналогичное утверждение для класса Р1Р до сих пор не удастся ни доказать ни опровергнуть: приведенное выше для ДМТ рассуждение нельзя обобщить на НДМТ, ибо для индивидуальных задач 1 с ответом "нет" (т.е. 1 ф Х(П), или 1 б Х(П)) НДМТ не останавливается за время, ограниченное полиномом от длины входа 1.

В часгности, не известна НДМТ, решаюшэл КМ за полиномиаяьное время, так как для нее не придумано подсказки полиномиальной длины (естественный вариант — показать все маршруты — не полиномиален); включение КМ б НР не доказано и не опровергнуто. УПРАЖНЕНИЕ 3. Доказать, что.задача распознавании простоты числа принадлежит классу со-Р1Р, т.е.

ПЧ б 1э1Р. Опгедклпнив 5. Массовая задача распознавания свойств называется алеющей ворожую яаракшсрзэацзю, если для нее выполнено П б 1э1Рйсо-1э1Р. Из утверждения 2 следует, что Р С НРГ1со-Р1Р. Современная гипотеза состоит в равенстве этих классов. Отсюда и термин "хорошая характеризапия", так как для подобных задач есть основания надеяться на возможность построения полиномиальных алгоритмов (см.

задачу ЛН вЂ” линейные неравенства — в разд.2):Однако для задачи ПЧ, обладающей хорошей характеризапией (для доказательства того, что ПЧ б НР, см. [2, с. 414]), детерминированного полиномиального алгоритма пока не найдено, несмотря на ее непосредственную практическую значимость. 11 2. Ззлач распознавания свойств — большое разнообразие, и для теории представляет интерес не только возможность их классификации, но и способы определения класса сложности одних задач на основе известного класса сложности других. Поэтому вводится базовое для теории сложности понятие волэкомвальяой сеодвмосяьв.

Опгкдклкник 6. Будем говорить, что массовая задача распознавания свойств П' с кодировкой е' волинемияльмо сводятся к задаче П с кодировкой е, если любая индивидуальная задача 1' б П' может быть сведена за полиномиэльное время к некоторой 1 б П с сохранением ответа. Формакьно существует функпия сводимости у: е'(1У(П')) — е(1У(П)), такая что у(е'('К(П'))) = е(1Г(П)), т.е. Ыо~ б е'('У(П')) у(п') б е(У(П)) и Ывн б е'(зу(П') ~ з'(П)) У(ам) б е(ЗЭ(П) ~ з (П)), и существует НМТ Аг, реализующая у за полнномиальное время, ,/ т.е. Вру(.) — поливом: Ые б е'(1У(П')) ~„((п() < ру(~п~).

В случае, когда соответствующие кодировки Не избыточны, будем использовать термин полиномиальной сводимости по отношению к самим задачам (без указания кодировок) и применять обозначение П'ос П. (Корректность упрощения вытекает из полиномиальной сводимости задачи к самой себе, но с другой неизбыточной кодировкой, и следу- . ющего очевидного утверждения — транзитивности отношения а.) Утвкгждкник 3.

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