В.Б. Алексеев - Введение в теорию сложности алгоритмов, страница 10

Обозначим через ~м(а~6) след при работе машины Тьюринга М на слове а6 в точке, разделяющей а и 6. Лемма 4.13. Пусть а,6, с — некотпорые слова и пусть см(а~6с) = см(а6~с). Тогда при работпе М на слове ас слева и справа отп точки, разделятотаеп и и с, машина работпаетп тпак же, как на соотпеетставуюших часптях при работе на а6с. Утверждение этой леммы вытекает из леммы 4.1. При работе машины Тьюринга на входном слове а = атаэ...о„ точкой т' будем называть точку после ячейки, в которой находится а;. Теорема 4.9.

Пустпь машина Тьюринга М распознаетп язык Ь С А". Пустаь Ым(п) — максимальная длина следов в тпочках 1,2,...,и при работпе матиины М на всех словах а и А" длины и, а Тм(п) максимальное время вычисления ( гасло шагов) машины М на словах длины и из А*. Тогда если выполтняетпся хотпя бы одно из двух условибт а) дм(п) = о(1об и); б) Тм(п) = о(п 1об и), тпо Ь вЂ” регулярный язык. Показатпельсшво теоремы (от противного). Йопустим, что Ь— не регулярный язык.

Тогда по теореме 4.8 дм(п) неограниченнея последовательность. По лемме 4.12тиэ нее можно выделить подпоследовательность пп пп... такую, что (4.1) дц(п) < Нм(ти) для всех и < и, (т = 1, 2,... ). Лемма 4.14. Пустпь пь тта... удовлетаворяютп (Д.1) и а, — слово длины пп на котором достигаетпсе дм(пт). Тогда при работае М на слове ат один и тпотп же след е тпочкае 1, 2,..., пт не может повторюпься более чем й раза.

Показатпельстпео. Предположим, что а; = а6сд и см(а(ад) = см(а6)саэ) = ~м(а6с(д), где а, 6, с — не пустые слова. При работе М на слове а; есть следы длины дм(тц). По крайней мере один такой след либо не лежит внутри 6, либо не лежит внутри с. Тогда по лемме 4.13 он сохранится при работе М либо на слове асЫ, либо на слове аь6тт, но это пРотиворечат тому, что Ым(п) < дм(п;) для всех и < па Лемма доказана.

Из этой леммы получаем, что при работе М на слове а; в точках 1,2,...,и, имеется не менее з разных следов. Тогда по леммам 4.10 и 4.11 дм(п~) > с1обз пз, и сумма длин этих разных следов, а значит и время работы машины М, не меньше, чем сгч 1ояз аз', где с — некоторая константа. Если вьлюлнено условие а) или б) из теоремы 4.9, то получаем протвворечие.

Следовательно, от противного, получаем, что при выполнении условия а) или б) язык В регулярен. Теорема 4.9 доказана. Следствие. Если Нм(п) = о(1ояп) и ш Тм(п) = о(п1ояп), то суиествуст машина Тьюринга (автомат) 1ь', распознаю|маг тот же .яэмк Ь, для которой Йн(п) = 1, Тн(п) = п+ 1. 4.5. Классы Р и УР Определение.

Пусть алгоритм осуществляет преобразование ю: А' -+ В' слов в алфавите А в слова в алфавите В. Тогда этот алгоритм называется полнномиальным (нлн имеющим полиномиальную сложность), если су|цествует полинам р(п) такой, что для любого натурального и время работы алгоритма на любом входном слове длины и не превосходит р(п). (При этом можно считать, что все хоэффьщиенты в р(п) неотрнцательны, то есть р(п) возрастающая функция.) Определение. Задачей распознавания называется любое отображение ьь: А* -+ (ьда", ьнеть). С любой задачей распознавания р можно связать язык Ц С А' следующим образом: а Е Ь л=ь ю: а -+ ьда".

И обратно, любой язык можно рассматривать как задачу распознавания. Определение. Класс Р— это класс всех языков (задач распознавания), для каждого из которых существует распознающий алгоритм с полиномнальной сложностью. Определение. Будем говорить, что язык Ь1 С А* полиномиально сводится к языку Вз С В', если существует полиномиальный алгоритм (например, машина Тьюринга) ~р: А" ь В', такой что ~р(а) Е Вз л=ь а Е Л1 Теорема 4.10.

Пусть Ь1 С А', Ьз С В', Вз Е Р и Ь| полиномиально сводится к л з. Тогда Ь| Е Р. Локазательство. По условию существуют машины Тьюринга М1 и Мз такие, что М1 полиномиально сводит Ь1 х Ьз, а Мз с полиномиальной сложностью распознает Ьз. Рассмотрим машину Тьюринга М = Мз(М1). Тогда М: А' -+ 1 ада", "неть), причем для любого слова а б А' имеем М(й) = да е= Мз(М1(а)) = "да" е=ь М1(а) б В с — ь о с В то есть М распознает язык 1 ь По условию время работы (число шатов) машин М1 и М на входных словах длины п не превосходит р1(п) и рз(л), где рь рз — полииомы. Тогда время работы М на слове а длины а не превосходит рз(л)+рз()М~(й)!), где )М1(а)) — длина слона Мд(а). Так как машина Тьюринга М| на каждом шаге может увеличивать длину слова не более чем на 1, то ~М|(а) ~ < и + рг(п) и время работы М на а не превосходит р1(п) + рз(п + р1(л)) = рз(л), где рз — поливом. (Здесь считается, что все коэффипненты в рз неотрипательвы н, следовательно, рз(п) — неубывающая функпия).

Тахим образом М распознает язык Ь1 с полиномнэльной сложностью. Теорема доказана. Эта теорема позволяет получать ползшомиальные алгоритмы для ° двих задач распознавания из имеющихся полиномизльных алгоритмов для других задач просто путем полиномизльного свелення одних задач к другим. К сожалению, для большинства задач, возникающих на практике, пока не известно, входят ли они в класс Р, но почти все такие задачи оказываются в другом классе, которьгй обозначают ИР. Определение.

Язык 1 С А' (задача распознавания) входит в класс 1У Р, если и только если существуют алфавит В, полипом д(п) и предвкат фт, у): А' х В" — > ("истина", "ложь" 1 такие, что Я(х, у) е Р н для любого слова а б А' выполняется; а б В е=э Лд б В'ЦЬ| < д(/а!)йЯ(а, Ь)) (здесь /а/ и 1Ь| — длина слов а и 6). Слово Ь называют сертификатом для слова а, а алгоритм, распознающий предикат Я(а, Ь), — алгоритмом проверки сертификата. Таким образом, если а б Ь (в задаче распознавания для входа а ответ "да"), то должно существовать быстрое подтверждение для этого, то есть должен существовать подтверждающий зто сертификат Ь (небольшой длины) и быстрый способ подтвердить, что это действительно подходялгий сертификат.

Если же а ф Ь, то такого 6 просто не должно существовать. Таким образом, ответы "да" и "нет", здесь не симметричны. Заметим также, что для случая а б В лишь утверждается существование сертификата 6, но ничего не говорится о сложности его нахпждення (если в В имеется т букв н (а! = л, то (Ь) < г(п) и число такж слав 6 не меньше, чем гжЯ~, то есть экспонендиально зависит от л), Рассмотрим примеры языков из 33Р.

КЛИКА. Вход: любой неориентировзлный граф О [7] и натуральное число Е Вопрос: Существует ли в графе С клика размера lс, то есть й вершин таких, что любая пара из них соединена ребром? Более строго, мы должны задать входной алфавит А и способ представления графов и числа й в этом алфавите. Можно, например, считать, что А = (О, 1,, ) и граф задается матрицей смежности (из О и 1), которая затем выписывается в одно слово подряд по строкам матрипы с разделителем; между строками матрицы. В конце после; записывается /с в двоичной системе. У'тверигдение.

КЛИКА Е МР. Локаэапэельспэво. В качестве сертификата 5 для вхопа а будем брать список из номеров й вершин, составляющих клику. Очевидно, 1Ь! < д((а~), где й — некоторый полипом. Преликат О будет обозначать, что данные вершины задают клику в данном графе и этих вершин ровно й. Пля распбзнавалия справедливости такого свонства 1~ легко построить алгоритм со сложностью, не превосходящей полинома от суммарной длины кода графа а и сертификата Е ГАМИЛЬТОНОВ ЦИКЛ (ГЦ).

Вход: лтобой неориентированный граф С. Вопрос: Существует ли в графе С гамильтонов цикл, то есть цикл, проходяпшй через каждую вершину ровно 1 раз? З'тверксденне. ГЦ Е ХР. Локаэагпеяъспэво. Сертификатом здесь является последовательность вз вершин оэ,оз,...,о,„. Предикат (,> выражает утверждение, что в этой последовательности все вершины графа встречаются ровно 1 раз и в графе есть ребра (оп ооы) для всех 1 = 1, 2,..., тп — 1, а также ребро (ом, оз).

Лля распознавания справедщ~вости такого свойства Р легко построить алгоритм со сложностью, не превосходящей полинома от суммарной длины кода графа а и сертификата 6. Определение. Коньюнктивной нормальной формой (КНФ) называется булева формула вида Р(хь..., х„,) = Р13сРз3с...3сРм где длк каждого д: Р; = Г11 ~' Г;.з Ч... Ч 1ьпэ и все 11 ь — либо пеРеменвые, либо отрицания переменных, причем каждая переменная встречается в одном Р не более одного раза. Выражения Р, называют дизъюнктами, а составляющие их Г? ь литералами.

ВЬШОЛНИМОСТЬ (ВЬШ). Вход: любая формула Р в вцде КНФ. 48 Вопрос: существует ли набор переменных (аь..., а,„), на котором Р(ап..., а ) = 1 (выполннма ли Р)? Утверждение. ВЫПЕ г?Р. Дохазашеаьстлво.. Сертификатом для входа Р является набор (аь...,а,„), на котором Р(аь...,а ) = 1. Предикат Я выражает тот факт, что данная формула Р на данном наборе (аь..., а ) действительно принимает значение 1.