Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 110
Текст из файла (страница 110)
Кроме того, проблема выполнимости остается ХР-полной, даже если вид формулы ограничен произведением сомножителей, каждый из которых содержит лишь три литерала (проблема ЗВЫП). + Другие ззР-полные проблемы. ХР-полнота очень многих проблем доказывается путем сведения к ним других проблем, о которых заранее известно, что они ХР- полные. Здесь приведены сведения, доказывающие ХР-полноту проблем незави- симого множества, узельного покрытия, ориентированного и неориентированного гамильтонова цикла, а также коммивояжера. 10.5.
РЕЗЮМЕ 477 1 0.6. Литература Понятие ХР-полноты как свидетельство того, что проблему нельзя решить за полиномиальное время, и доказательство ХР-полноты ВЫП, ВКНФ и ЗВЫП впервые были приведены в работе С. Кука !3!. За ней последовала не менее важная статья Р. Карпа 161, в которой было показано, что ХР-полнота — это не изолированный феномен; она присуща многим трудным комбинаторным проблемам, изучавшимся долгие годы в исследовании операций и других дисциплинах.
Из этой статьи взяты все проблемы, ХР-полнота которых доказана в разделе 10.4 — независимое множество, узельное покрытие, гамильтонов цикл и коммивояжер. Кроме того, в ней можно найти решения некоторых проблем, рассмотренных в упражнениях: реберное покрытие обратных связей, разбиение, раскраска и точное покрытие. В книге Гэри и Джонсона 14] собрано воедино большое число фалтов, касающихся ХР-полноты различных проблем, а также приведены их частные случаи, разрешимые за полиномиальное время. В 15! содержатся статьи об аппроксимации решения ХР-полной проблемы за полиномиальное время. Необходимо упомянуть еше несколько работ, послуживших серьезным вкладом в теорию ХР-полноты.
Первые исследования классов языков, определяемых временем работы машин Тьюринга, были предприняты Хартманисом и Стирнзом (8!. Кобхем [2! первым выделил класс Р как понятие, в котором отражено коренное отличие от алгоритмов, имеющих конкретное полиномиальное время работы, например О(и ). Несколько 2 позже (но независимо) идею ХР-полноты исследовал Левин !7].
ХР-полнота задачи линейного целочисленного программирования (упражнение 10.4.4, в) появилась в работе 111, а также в неопубликованных заметках Дж. Гатена (3. ОагЬеп) и М. Зивекинга (М. 5!еиеЫп8), ХР-полнота проблемы расписания с единичным временем выполнения (упражнение 10.4.4, ж) доказана в !9!. 1. 1. Вогоьй апд 1.. В. ТгеуЬ!8, "ВоцпсЬ оп роз!!гке !и!е8га! зо1ибоп оГ Ипеаг !3!орЬап!1пе ес!иа!!опз", Ргосеег!гийз о!'гйе АМо" 55 (1976), рр. 299-304. 2. А.
СоЬЬаш, "ТЬе !и!плейс согорша!юпа1 ЙШсц!!у о( бзпсг!опз", Ргос.7964 Сол8гезз 7ог Соя!с, Майетаггсл, апг! йе РЬ!!озорф о/ос!енсе, ХопЬ Но!!апд, Азиз!егбаш, рр. 24-30. 3. 5. С. Соо1с, "ТЬе сошр1ехйу оГ 1Ьеогеш-ргои!п8 ргосе0цгез", ГЫгг! АСМ Яутроаит ои ГЬеогу оГСотригт8 (197!), АСМ, Хе~и УогЬ, рр. 151-158. (Кук С. Сложность процедур вывода теорем. — Кибернетический сборник, новая серия, вып. 12. — М.: Мир, ! 975. — С.
5-15.) 4. М. К. Оагеу апд (3. 3. )оЬпзоп, Сотригегз аль 7иггасгаЬг!!!уг а ОиЫе го йе ТЬеогу о~' ЫР-Сотр!егепезз, Н. Ргеешап, Хезт т'огк, !979. (Гэри М.„Джонсон Д. Вычислительные машины и труднорешаемые задачи. — Мэ Мир, ! 982.) 478 ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ ГЛАВА 11 Дополнительные классы проблем Труднорешаемые проблемы не ограничиваются классом А(Р. Существует много других классов труднорешаемых проблем, по разным причинам представляющих интерес.
Некоторые вопросы, связанные с этими классами, вроде Р = ЛР, остаются нерешенными. Вначале рассматривается класс, тесно связанный с Р и ЛР, — класс дополнений языков из ЛР, часто называемый "со-АгР'. Если Р = ЛгР, то со-А(Р равен обоим, поскольку Р замкнут относительно дополнения. Однако более вероятно, что со-АГР отличается от обоих этих классов, и ни одна ЛР-полная проблема не принадлежит со-ЛР. Далее изучается класс РЯ Он образован проблемами, которые решаются иа машинах Тьюринга с использованием объема ленты, полипом иального относительно длины входа.
Этим машинам Тьюринга разрешается использовать экспоненциальное время, но ограниченную часть ленты. В отличие от ситуации с полиномиальным временем, здесь мож- но доказать, что при таком же ограничении пространства иедетерминизм не увеличивает мощности МТ. Однако, несмотря на то, что РБ очевидным образом включает Л'Р, неизвестно, равны ли эти классы.
Ожидается, что они не равны, и здесь мы опишем проблему, которая полна для Р$ и предположительно не принадлежит Л'Р. Затем обратимся к рандомизированным алгоритмам и двум классам языков, лежащим между Р и ЛР. Один из этих классов обозначается Р.Р ("гаврош ро!упош(аГ'!апяцаяез— "случайные полиномиальные" языки). Эти языки имеют алгоритм, который работает полиномиальное время, используя "бросание монеты" или (на практике) генератор случайных чисел. Алгоритм или подтверждает принадлежность входа языку, или отвечает "не знаю". Кроме того, если вход принадлежит языку, то существует некоторая вероятность больше О, что алгоритм будет "докладывать об успехе", поэтому его повторное применение будет с вероятностью, близкой к 1, подтверждать принадлежность.
Второй класс, называемый ЯРР (лего-еггог, ргоЬаЬ1! нйс ро1упопиа! — безошибочные, вероятностные полиномиальные), также использует рандомизацию, но алгоритмы для языков этого класса отвечают: "да, вход принадлежит языку*' или "нет, не принадлежит". Ожидаемое время работы алгоритма полиномиально. Однако возможно выполнение алгоритма, требующее больше времени, чем полиномиальное.
Чтобы увязать приведенные понятия, рассмотрим важный вопрос проверки простоты. Многие современные системы шифрования основаны на следующих свойствах. 1. Способность быстро находить большие простые числа, чтобы защитить от посторонних воздействий канал сообшения между компьютерами. 2. Предположение о том, что разложение на целые сомножители требует экспоненциалы ного времени, измеряемого в виде функции от длины и двоичной записи целого числа. Будет показано, что проверка простоты чисел принадлежит как Л'Р, та и со-МР, поэтому вряд ли удастся доказать ХР-полноту этой проверки.
Это плохо, так как доказательство ХР-полноты является наиболее действенным доводом в пользу того, что проблема, скорее всего, требует экспоненциального времени. Будет показано также, что проверка простоты принадлежит классу ЕР. Это и хорошо, и плохо. Хорошо, поскольку системы шифрования, использующие простые числа, применяют для их поиска алгоритм из класса Т'Р.
Плохо, так как подтверждается предположение, что доказать ХР-полноту провер- ки простоты так и не удастся. 11.1. Дополнения языков из Л/Р Класс языков Р замкнут относительно дополнения (см. упражнение ! 0.1.6). Это легко обосновать. Пусть | принадлежит Р, а М вЂ” МТ для Ь. Для допускания Х изменим М: введем новое допускающее состояние д и новые переходы в д из тех состояний, в которых М останавливается, не допуская.
Сделаем исходные допускаюваие состояния недо- пускающими. Тогда измененная МТ допускает Х и работает столько же времени, сколько М, с возможным добавлением одного перехода. Таким образом, Х принадлежит Р, если 1. принадлежит Р. Неизвестно, замкнут ли класс ЛР относительно дополнения, но похоже, что нет.
В частности, можно ожидать, что если язык Хр-полон, то его дополнение не принадлежит ЛР. 11Л.1. Класс языков со-Л'Р Со-ЛР— это класс языков, дополнения которых принадлежат ЛР. Напомним, что дополнение любого языка из Р также принадлежит Р и, следовательно, Л'Р. С другой стороны, мы верим, что дополнения ХР-полных проблем не принадлежат МР, поэтому в со-ЛР нет ни одной ХР-полной проблемы. Аналогично мы верим, что дополнения ХР- полных проблем, по определению содержашиеся в со-Л'Р, не находятся в ЛР. На рис. 11.1 показана предполагаемая взаимосвязь этих классов.
Однако не следует забывать, что если Р окажется равным ЛгР, то все три класса совпадут. Пример 11.1. Рассмотрим дополнение языка ВЫП, которое принадлежит со-Л'Р и обозначается НВЫП (невыполнимая). НВЫП включает все коды невыполнимых булевых формул, а также цепочки, которые не являются кодами допустимых булевых формул. Мы верим, что НВЫП не принадлежит ЛР, но доказать зто не можем.
482 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ ЕЛАССЪ| ПРОБЛЕМ ыепроблвмы нил ИР-полных проблем Рис. ! ! !. Предпояагаелзая взаимосвязь между со геРи другичч классами языков Еще одним примером проблемы, которая предположительно находится в со-ЛР, ио ие в ЛР, служит язык ТАВТ вЂ” множество всех (закодироваииых) булевых формул, являющихся тавтологиями, т.е. истинных при любой подстановке. Заметим, что формула Е является тавтологией тогда и только тогда, когда — Е невыполнима. Таким образом, ТАВТ и НВЫП связаны так, что если булева формула Е принадлежит ТАВТ, то ~Е принадлежит НВЫП, и наоборот. Однако НВЫП содержит также цепочки, ие представляющие допустимые выражения, тогда как все цепочки в ТАВТ вЂ” лопустимые. СЗ 11.1.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
