Конспект установочных лекций по комплексному курсу Информатика, Теория информации




Временная и ленточная сложность задач - часть 3


NTIME(T(n)) === NTIME(cT(n)).

Предыдущая теорема показывает, что для вопроса о сложности прежде всего интересен порядок функции Т(n).

Важным вопросом является взаимосвязь между DTIME и NTIME, а также между DSPACE и NSPACE. Для ленточной сложности ответ дает теорема Савича (Sawitch). Для формулирования этой теоремы понадобится следующее определение. Функция

S: N > N называется вполне ленточно-конструируемой (конструируемой по памяти), если существует S(n)-ленточно-ограниченная Т-машина, для которой справедливо: для всех чисел nÎ N существует входное слово длины n, для которого Т-машине действительно требуется S(n) ячеек памяти. Аналогично определяется и вполне временно конструируемая функция (конструируемая по времени).

Теорема (по Савичу). Каждая проблема распознавания из NSPACE (S(n)) принадлежит также DSPACE (S(n)2), если S является вполне ленточно-конструируемой и "n Î N: S(n)³ Log(n).

Доказательство. Пусть М1 есть S(n)-лeнтoчнo-oгpaничeннaя Т-машина. Существует константа с Î N, такая, что для всех чисел n Î N справедливо высказывание: Т-машина останавливается самое большее через с^ (при ^=S(n)) шагов, так что существует самое большее с^) конфигураций для входного слова длины n.

Вычисление недетерминированной Т-машины есть трасса (ветвь) в дереве, приведенном на рис. 10.1. При этом для допускаемого слова существует ветвь, на которой нет повторяющихся узлов.

                                            K0

                          å     æ

                                  k1     ….      Kn1

                                        å..æ       å..æ




Содержание  Назад  Вперед