11. НЕКОТОРЫЕ ДОКАЗУЕМО ТРУДНО РАЗРЕШИМЫЕ ЗАДАЧИ

В этой главе мы приводим доказательства того, что для двух классов расширенных регулярных выражений задача пустоты дополнения трудно разрешима, т. е. любой алгоритм, решающий ее для любого из двух классов, тратит по меньшей мере экспоненциальное время. Для одного из этих классов устанавливается нижняя оценка, существенно превышающая экспоненту. В частности, будет показано, что эта задача требует времени, большего чем

для любой конечной башни из двоек. Прежде чем устанавливать нижние оценки, мы рассмотрим результаты о иерархиях, показывающие, что "чем больше времени или памяти можно использовать для вычислений, тем больше языков можно распознать".

11.1. ИЕРАРХИИ ПО СЛОЖНОСТИ

В гл. 10 мы видели, что некоторые задачи полны для недетерминированного полиномиального времени или же для полиномиальной памяти. Чтобы доказать полноту конкретных задач, мы показывали, как в терминах данной конкретной задачи представляется произвольная задача из класса или

Техника доказательств представляла собой, по существу, технику моделирования. Например, мы показали, что задача выполнимости булевых формул NP-полна, а задача пустоты дополнения для регулярных выражений полна для полиномиальной памяти, причем в обоих случаях результат получался прямым вложением вычислений на машинах Тьюринга в частные случаи этих задач. Полноту других задач мы показали, сводя к ним какую-нибудь задачу, о которой уже известно, что она полна для соответствующего класса задач. Таким образом, мы показали, что оба класса и

содержат "самые трудные" задачи, т. е. задачи, сложность которых по меньшей мере столь же велика, как и сложность любой задачи из этого класса.

Однако сколь ни сильны косвенные доводы, еще никому не удалось найти в или задачу, о которой можно было бы доказать, что она не принадлежит Более того, похоже, что техники гл. 10 хватает лишь для доказательства того, что данная задача по меньшей мере столь же трудна, как и любая другая задача из некоторого класса. Чтобы действительно доказать, что данная задача не принадлежит нужна техника, которая позволила бы показать, что существует хотя бы один язык, не допускаемый никакой детерминированной машиной Тьюринга за полиномиальное время. Чаще всего для подобной цели применяется диагонализация. Хотя этот способ, по-видимому, не достаточно силен, чтобы доказать, что с его помощью удалось получить результаты о иерархии как по емкостной, так и по временной сложностям для обоих типов машин Тьюринга — детерминированных и недетерминированных. Каждая теорема о иерархии имеет следующий вид: для данных "хороших" функций таких, что растет "быстрее" существует язык со сложностью но не