Cтраница 2
Чтобы действительно доказать, что данная задача не принадлежит JP-TIME, нужна техника, которая позволила бы показать, что существует хотя бы один язык, не допускаемый никакой детерминированной машиной Тьюринга за полиномиальное время. Чаще всего для подобной цели применяется диагонализация. Хотя этот способ, по-видимому, не достаточно силен, чтобы доказать, что - TIME off - TIME, с его помощью удалось получить результаты о иерархии как по емкостной, так и по временной сложностям для обоих типов машин Тьюринга - детерминированных и недетерминированных. [16]
Это определение представляется более узким, чем предыдущее, хотя не известно, приводят ли указанные два определения NP-полных языков к разным классам. Определение, основанное на сводимости, означает, что если М0 - детерминированная машина Тьюринга, распознающая NP-полный язык L0 за время Т ( п), то всякий язык из ЖЗ можно распознать за время Т ( р ( п)), где р - некоторый полином, с помощью детерминированной машины Тьюринга, которая обращается к Мй как к подпрограмме нуль или более раз. [17]
В-третьих, машины Тьюринга позволяют задавать проблемы, требующие ответа ДА-НЕТ в виде распознавания языков, состоящих из описаний проблем с ответом ДА. Сводимость одной проблемы к другой означает трансформацию языка первой проблемы к некоторому подмножеству языка второй проблемы. Эта трансформация также осуществляется некоторой детерминированной машиной Тьюринга. [18]
Если L - некоторый формальный язык, распознаваемый некоторой программой М детерминированной машины Тьюринга, а временная сложность М ( см. С. [19]
Если никакая последовательность шагов не приводит к допусканию входа, то детерминированное моделирование машины М могло бы продолжаться бесконечно долго, если только нет какой-нибудь априорной границы на длину кратчайшей допускающей последовательности. Поэтому естественно ожидать, что недетерминированные машины Тьюринга способны выполнять задания, которые никакие детерминированные машины Тьюринга не могут выполнить за то же время или с той же памятью. Тем не менее все еще открыт важный вопрос о существовании языков, допускаемых недетерминированной машиной Тьюринга с данной временной или емкостной сложностью, но не допускаемых никакой детерминированной машиной Тьюринга с той же сложностью. [20]
Ключевое понятие в теории NP-полных задач - НМТ [16], для которых каждый шаг может иметь конечное число различных продолжений. При данном входном слове X можно считать, что НМТ М параллельно выполняет все возможные последовательности шагов, пока не достигнет заключительного ( допускающего) состояния ( в этом случае X называется допускаемым) или пока не окажется, что дальнейшие шаги невозможны. Если а - кратчайшая последовательность шагов, которая оканчивается допускающим состоянием, то, как только машина М сделает о шагов, она остановится. Часто удобно представлять, что М угадывает только шаги из последовательности а. Поэтому естественно ожидать, что НМТ способны выполнять задания, которые никакие детерминированные машины Тьюринга не могут выполнить за то же время или с той же памятью. [21]
Стирнза не является конструктивным. А) требует экспоненциальной памяти, а следовательно, и времени. Идея доказательства этого факта состоит в следующем. Строится детерминированный алгоритм моделирования, который по данной машине Тьюринга, входу и экспоненциальной оценке памяти строит регулярное выражение, представляющее вычисление на заданной машине при данном входе. Это выражение задает регулярное событие ( О V 0 тогда и только тогда, когда машина Тьюринга не принимает данный вход в пределах выбранной оценки памяти. Отсюда следует, что проблема эквивалентности регулярных выражений с возведением в квадрат так же трудна, как любая проблема, разрешимая детерминированной машиной Тьюринга с экспоненциальной памятью. [22]