1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 91
Текст из файла (страница 91)
е. задача принадлежности цепочки произвольному контекстному языку полна для о.-БРАСЕ. 10.28. Покажите, что задача эквивалентности двух регулярных выражений полна для полиномиальной памяти. **10.29. Опишите алгоритм, допускающий множество Ь, кодов всех регулярных выражений )с, представляющих непустое множество, который можно реализовать на ДМТ с линейно ограниченной памятью. Проблемы для исследования 10.30. Одна из очевидных открытых проблем — выяснить, выполняются ли равенства о'-Т1МЕ=е))'о--Т1МЕ и е!)Го'-Т1МЕ= =У-БРАСЕ. Если учесть объем работы, проделанный в поисках алгоритмов, решающих )ч)Р-полные задачи за полиномиальное время, то похоже, что эта проблема по меньшей мере столь же сложна, как некоторые классические проблемы математики, такие, как гипотеза Ферма (иИмеет ли уравнение хо+у"=г" решение в целых числах для л)39п) или проблема четырех красок ').
з) В Вни. Атею Маиь Юос., 52, № 5 (1976), 711 — 712, опублнковапо сообшенне о решении проблемы четырех красок, которое нашли с помошью ЭВМ амернканскне математнкв Аппель н Хакен: Более подробное изложение нх результатов см. в Пипоы 7. Мосй., 21, № 3 (1977), 429 — 567.— Прим. Ред. 15 А. Ахо, Дж Хопкро)ж, Дж Упьмав ГЛ. !Е. ЯР.ПОЛНЫЕ ЗАДАЧИ !0,31. В случае неудачи с 10.30 было бы интересно получить нетривиальный результат, дающий такую функцию Т(п), что всякий язык из [[ГЗ.-Т]МЕ распознается детерминированной машиной с временной сложностью не более Т(п).
Это не показано даже для Т (а) =2л. Замечания но литературе Дополнительную информацию о недетермннированных машинах Тьюринга можно найти в книге Хопкрофта, Ульмана [1969). Теорему 10.1, устананлннаю. шую связь между емкостными сложностями детерминированных и недетерминированных машин, доказал Савич )1970].
Ключевая теорема о ]ЧР-полноте задачи выполнимости принадлежит Куку [197!6). Много классических ]ЧР-полных задач привел Карп 1!972], ясно про. демонстрировав важность понятия [ЧР-полноты. С тех пор к семейству известных ]ЧР-полных задач были добавлены новые, найденные Сахни [1972), Сети [1973), Ульманом [1973), Раундзом [1973), Ибаррой, Сахнн 1!9731, Хантом, Розенкранцем [!974), Гэри, Джонсоном, Стокмейером [1974], Бруно, Сети [19741 и многими дру.
гимн. Интересно, что до Кука в нескольких работах была показана полиноми. альная взаимосвязь иежду некоторымн ]ЧР.полными задачами, но объем всего класса не был осознан. Например, Данциг, Блаттнер, Рао [!966) установили связь между задачами о коммивояжере и о кратчайшем пути с неотрицательными ве. сами. Днветти, Грасселли [!968] описали связь между задачами о покрытии множествами и о множестве ребер, разрезаюших циклы.
Задачи, полные для Я-ЬРДСБ, впервые рассмотрелн Мейер, Стокмейер [1972]. Первый язык, полный для памяти, неявно описал Сэзнч [197!), определив язык (множество проходимых лабиринтов), полный для 1оя и-памяти. Джоунс [!973) и Стокмейер, Мейер [1973) рассмотрели ограниченные формы сводимостн задач за полиномиальное время. Бук [1972, !9741 доказал несравнимость некоторых классов сложности, Упр. 10.8 и 10.9 взяты у Кука [19716], упр. 10.10 и 10.12 — у Карпа [19721, упр. 10.13 — у Стокмейера, Мейера [!973) и Ханта [1973а], упр. 10.!4 и 10.2в 8— у Стокмейера, Мейера [!9731, а упр.
1О.!5 — 10.18 — у Гэри, Джонсона, Стокмейерз [1974]; рис. 10.14 представляет собой улучшенный вариант, предложенный Фишером. Доказательство ]ЧР-полноты задачи 3-раскрашиваемости планарных г г афон появилось в работе Стокмейера [19731. Упр. 10.20 заимствовано из работы вена [1973), упр. 10.21 — Ульмана [1973), упр. 10,26 — Кука [19716], а редукция, нужная для решения упр. 10.27, взята у Карпа 1!9721. Доказательство теоремы 10.13 предложил нам Ивен. НЕКОТОРЫЕ ДОКАЗУЕМО ТРУДНО РАЗРЕШИМЫЕ ЗАДАЧИ В этой главе мы приводим доказательства того, что для двух классов расширенных регулярных выражений задача пустоты дополнения трудно разрешима, т. е. любой алгоритм, решающий ее для любого из двух классов, тратит по меньшей мере экспоненциальное время.
Зля одного из этих классов устанавливается нижняя оценка, существенно превышающая экспоненту. В частности, будет показано, что эта задача требует времени, большего чем ,в для любой конечной башни из двоек. Прежде чем устанавливать нижние оценки, мы рассмотрим результаты о иерархиях, показывающие, что "чем больше времени или памяти можно использовать для вычислений, тем больше языков можно распознать". $5.5. ИЕРАРХИИ ПО СЛОЖНОСТИ В гл.
10 мы видели, что некоторые задачи полны для недетерминированиого полиномиального времени или же для полиномиальиой памяти. Чтобы доказать полноту конкретных задач, мы показывали, как в терминах данной конкретной задачи представляется произвольная задача из класса Д'У-Т1МЕ или У-БРАСЕ. Техника доказательств представляла собой, по существу, технику моделирования.
Например, мы показали, что задача выполнимости булевых формул НР-полна, а задача пустоты дополнения для регулярных выражений полна для полиномиальной памяти, причем в обоих случаях результат получался прямым вложением вычислений иа машинах Тьюринга в частные случаи этих задач. Полноту других задач мы показали, сводя к ним какую-нибудь задачу, о которой уже известно, что она полна для соответствующего класса задач. Таким образом, мы показали, что оба класса ч'з'-Т1МЕ и Р-БРАСЕ 15$ ° 5$ гл.
и. некотоеыв тгудно глзгишимые зхдлчи содержат "самые трудные" задачи, т. е. задачи, сложность которых по меньшей мере столь же велика, как и сложность любой задачи из этого класса. Однако сколь ни сильны косвенные доводы, еще никому не удалось найти в М'У-Т1МЕ или У-БРАСЕ задачу, о которой можно было бы доказать, что оиа ие принадлежит У-Т1МЕ.
Более того, похоже, что техники гл. 10 хватает лишь для доказательства того, что данная задача по меньшей мере столь же трудна, как и любая другая задача из некоторого класса. Чтобы действительно доказать, что данная задача ие принадлежит У-Т1МЕ, нужна техника, которая позволила бы показать, что существует хотя бы один язык, не допускаемый никакой детерминированной машиной Тьюринга за полиномиальное время.
Чаще всего для подобной цели применяется диагонализация, Хотя этот способ, по-видимому, ие достаточно силен, чтобы доказать, что У-Т1МЕФ,(ГУ-Т1МЕ, с его помощью удалось получить результаты о иерархии как по емкостной, так и по временной сложностям для обоих типов машин Тьюринга — детерминированных и недетерминированиых, Каждая теорема о иерархии имеет следующий вид: для данных "хороших" функций Г(л) и д(п), таких, что Г(п) растет "быстрее'* д(п), существует язык со сложностью 1(п), но не д(п).
11.?. ИЕРАРХИЯ ПО ЕМКОСТНОЙ СЛОЖНОСТИ ДЛЯ ДЕТЕРМИНИРОВАННЫХ МАШИН ТЬЮРИНГА Здесь мы докажем теорему о иерархии по емкостной сложности (иерархии по памяти) для детерминированных машин Тьюринга. Можно доказать аналогичные результаты для времени и для недетерминированных машин Тьюринга, но поскольку для наших целей они не нужны, мы оставляем их в качестве упражнений. Вспомним, что в силу следствия 3 леммы 10.1, если язык Ь допускается й-ленточной ДМТ с емкостной сложностью Б (и), он допускается и одно- ленточной ДМТ с емкостной сложностью 5(а). Таким образом, можно ограничиться рассмотрением одноленточных ДМТ.
Чтобы получить результат о иерархии по емкостной сложности„ надо перечислилв ДМТ, т. е. каждому неотрицательному целому числу 1 поставить в соответствие единственную ДМТ. Кроме того, каждая ДМТ должна появляться в этом перечислении бесконечно много раз. Мы будем перечислять только одноленточные ДМТ с входным алфавитом (О, '! ), ибо это все, что иам нужно. Для перечисления всех машин Тьюринга достаточно просто обобщить этот метод, Не умаляя общности, можно принять следующие соглашения о способе представления одноленточных ДМТ. 1.
Состояния имеют имена дь д„.. „д, для некоторого з, причем д, — начальное и д, — допускающее состояния. 433 ИИА ИЕРАРХИЯ ПО ЕМКОСТНОЙ СЛОЖНОСТИ ДЛЯ ДМТ 2. Входным алфавитом служит (О, 1). 3. Ленточным алфавитом служит (Х„Х„..., Х,) для некоторого 1, где Х1=Ь, Х,=О и Хо=! 4.
Функция переходов 6 представляет собой список пятерок вида (ди Хь дд, Хи О ), означающих, что б(дь Хт)оо =(дд, Х,, 0 ), где д, и до — состояния, Хр и Х, — ленточные символы и 0„— направление сдвига головки: 1. (влево), й (вправо) н 5 (остается на месте) прн т=О, ! и 2 соответственно. Считаем, что такая пятерка кодируется цепочкой 1О'10~10А10'10"'1, б. Сама машина Тьюринга кодируется цепочкой, получающейся конкатенацией в любом порядке кодов пятерок, представляющих ее функцию переходов.
Спереди можно добавлять, если надо, дополнительные единицы. Результатом такого кодирования будет начинающаяся с единнцы цепочка из нулей и единиц, которую можно интерпретировать как целое число. Любое целое число, которое нельзя декодировать, считается представлением тривиальной машины Тьюринга с пустой функцией переходов. Каждая одноленточная ДМТ будет появляться в этом перечислении бесконечно много раз, поскольку, имея какую-то ДМТ, можно к началу ее кода приписывать единицы и получать все ббльшие н ббльшие целые числа, представляющие одно н то же множество пятерок.
Построим четырехленточную ДМТ М„рассматривающую свою входную цепочку х одновременно как код одноленточной ДМТ М н как вход для М. 1т(ы построим М, так, чтобы для каждой ДМТ М с данной сложностью нашлась хотя бы одна входная цепочка, которую допускает М„но отвергает М, нлн наоборот. Одна из способностей, которыми наделена машина М„состоит в возможности моделировать произвольную машину Тьюринга по ее описанию, Машина М, будет распознавать, допускает ли машина Тьюринга М входную цепочку хтак, что при этом используется неболее 5,(1х() клеток, где 5, — некоторая функция. Если М допускает х, укладываясь в 5,(~х!) клеток, то М, не допускает х. В противном случае М, допускает х.
Таким образом, либо поведение машины М, отличается от поведения 1-й ДМТ на входе х, являющемся двоичным представлением числа 1, либо 1-я ДМТ на входе х использует более 5,(!х!) клеток. Говорят, что М, представляет диагоналпзацию по всем ДМТ с емкостной сложностью 5,(п), нбо если вообразить двумерную таблицу, (1, 1)-й элемент которой показывает, допустила ли 1-я машина Тьюринга вход!, то поведение машины М, будет отличаться от поведения некоторых машин Тьюринга на диагонали этой таблицы. В частности, М, будет отличаться от машин Тьюринга, допускающих свой вход с емкостной сложностью, не большей 51(а).
В силу след- 453 1Э» А. Аоо. дж. Хооорарт, длс. Уоьмаа ГЛ. 11. НЕКОТОРЫЕ ТРУДНО РАЗРЕШИМЫЕ ЗАДАЧИ ствия 3 леммы 10.1 существует одноленточная ДМТ М„', эквивалентная М, и имеющая ту же емкостиую сложность Поскольку сама машина М; тоже представлена в таблице (скажем, это й-я ДМТ при некотором Й) и она не может отличаться от себя, то можно заключить, что емкостиая сложность машин М, и М; не есть 5,(л). Фактическая конструкция М, усложнена из-за нашего желания построить М, так, чтобы она имела такую емкостную сложность 5, (л), что 5,(л) и 5,(а) почти одинаковы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
