Лекции: С.А. Ложкин - Лекции по основам кибернетики (2016)

Файл скачан с сайта StudIzba.com

При копировании или цитировании материалов на других сайтах обязательно используйте ссылку на источник

Распознанный текст из изображения:

для вычисления всех п- достаточно 2" 1 сложений и одного вычид

тания достаточно для вычисления Т„после решения двух подзадач. Переходя к М, имеем Ь'р(Х) 2Ь,рЯ) + 0(Х). Отсюда по теореме 2.4 о рекуррентном неравенстве получаем Ь„р(Ж) = 0(Ю1ояЮ) (в этой теореме имеем а = 2,с = 2,а = 1). Отметим, что исходная задача была для и~ Е 10, 1). Однако в подзадачах переменные могут быть произвольными натуральными числами. Переход к подзадачам делается и — 1 раз Прй каждом переходе разрядность переменных увеличивается не более, чем на 1, поэтому в подзадачах все числа имеют длину не более и + 1. При и = О получаются подзадачи вычисления То вида То =- г ~ л я ... ~ = я, в которых образуются числа длины < т(п + 1). При переходе к задаче из подзадач длина чисел увеличивается не более, чем на 1, поэтому все числа в алгоритме имеют длину не более т(а+ 1) + и '-' сои81 и,. Следовательно, каждая арифметическая операция требует 0(а~) = 0(1од~ Х) битовых операций, откуда А(Х) = Т,,р~1~Г) . 0(1од~ И) = 0(Х 1од~ И). Теорема доказана.

32

4. Общая теория сложности задач

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

4.1. Машины Тьюринга

Машина Тьюринга М имеет потенциально бесконечную ленту, разделенную на ячейки, и головку, которая в каждый (дискретный) момент времени 1 = О, 1, 2,... обозревает ровно одну ячейку. Задано некоторое конечное множество состояний Я = (др, 01,..., дД, и машина в каждый момент времени находится ровно в 1 из этих состояний. Задан конечный ленточный (рабочий) алфавит С = 1со, с1,..., с ), где со — — Л вЂ” пустой символ, и в каждый момент времени в каждой ячейке находится ровно 1 символ из алфавита С, причем будем считать, что символы, отличные от Л, находятся лишь в конечном числе ячеек. Машина М характеризуется ее программой, которая представляет собой конечный набор команд вида: с,д, -+ с~д„Т, где с, Е С, сь ~ С, д, Е Я, д„Е Я, Т Е (Ь, В, Я1. На каждом такте машина М работает следующим образом. Если головка обозревает ячейку, в которой находится символ с;, М находится в состоянии ц и в программе машины М есть команда с;щ — ~ с~д„Т, то символ в обозреваемой ячейке заменяется на с~, машина переходит в состояние о„и головка остается на месте, если Т = Я, или сдвигается на 1 ячейку вправо или влево, если Т = В или Т = Ь. Далее машина переходит к следующему такту и повторяет этот процесс. Если же в программе машины нет команды, в левой части которой стоит пара с;щ, то машина останавливается.

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

Определение. Если А — алфавит, то через А* будем обозначать множество всех (конечных) слов в алфавите А. Пусть С вЂ” ленточный алфавит машины М, Со — — С ~ 1Л1 и пусть задан некоторый входной алфавит А, такой, что А С Со. Тогда мы будем считать, что машина М осуществляет преобразование <рм .. А* -+ Со 0 (*), которое определяется следующим образом (здесь * в (~~ трактуется как неопределенность). Пусть задано некоторое слово а = а1а2... а„б А'. Разместим символы этого слова в последовательные ячейки ленты, а в остальные

зз

Распознанный текст из изображения:

ячейки поместим Л, поместим головку на ячейку, в которой стоит а1, установим машину в начальное состояние о1 и начнем работу машины. Если после этого машина М будет работать бесконечно долго, то считаем, что уды(а1а3... а„) = ~. Если машина М остановится и на ленте все символы равны Л или между символами алфавита Со будет встречаться Л, то также ~рм(а1а3... а„) = ж. Если же после остановки машины М все символы алфавита Со на ленте стоят подряд, образуя слово 6, то ущ(а) = 6.

Тезис Тьюринга. Для любого алгоритмического преобразова- ниЯ У; А* -+ Со 0 1*) сУществУетп машина ТьюРинга М, осУщестпвляющая преобразование ~р.

4.2. Существование сложных задач

Рассмотрим все машины Тьюринга, имеющие в ленточном алфавите символы Л и ~. Пусть Я+ = (О) 0%, где й — множество натуральных чисел. Будем представлять число й е У+ на ленте машины в виде кода Л ~~ ... ~ Л, где количество ~ равно /с+ 1 (остальные символы на ленте Л). Набор (Й1,Й3,..., й„) будем представлять в виде кода Л ~~ ... ~ Л Й ... ~ Л... Л Й ... ~ Л, где в первом массиве к1 + 1 символов ~, во втором 12+ 1 и т.д. Применяя машину М к коду числа или набора, будем помещать головку на самый первый символ ~ и устанавливать машину М в ее начальное состояние о1.

Определение. Для любой машины Тьюринга М и любого натурального числа и будем считать, что машина М вычисляет функцию Дхь х3,..., х„): (Я~)" — ~ Я+ 0 (*) которая определяется следующим образом. Применим машину М к коду набора (а1, а3,..., а„). Если М остановится и после остановки на ленте будет только код некоторого числа 6 Е Я+, то ~(а1, а2,..., а„) = 6. Во всех остальных случаях Да1, а3,..., а„) = * (неопределенность).

Определение. Функция Дх1,хз,..., х„): (У+)" — ~ Я+ О 1*) называется вычислимой, если существует машина Тьюринга М, которая ее вычисляет.

Определение. Говорят, что машина М правильно вычисляет функцию Дх1,х3,...,х„), если, начиная работу с кода набора (а1,..., а„), машина М в том случае, когда ~(а1,аз,...,а„) не определено, обязательно работает бесконечно долго, а в том случае, когда Да1, аз,..., а„) = 6, машина останавливается, на ленте остается код Ь и головка машины обозревает самый левый символ ~.

Утверждение. если ~(х1, х3,..., х„) вычислима, то существует машина Тьюринга М, которая ее вычисляет правильно.

Доказательство см., например, в [18].

Определение. Всюду определенные вычислимые функции мы будем называть общерекурсивными функциями. (Обычно общерекурсивные функции определяют иначе, но данное определение эквивалентно обычному; см., например, [18]).

Функция, вычисляемая мадпиной М, не изменится, если произвольно переименовать все символы ленточного алфавита, кроме ~ и Л, и все состояния, оставляя начальное состояние начальным (конечно, разные символы должны переименовываться в разные). Поэтому мы будем считать, что есть бесконечный фиксированный алфавит 1со = Л, с1 =~, сз, сз,... ), из которого берется ленточный алфавит машины М, и бесконечный фиксированный алфавит ~до, д1, о~,... ), из которого берутся состояния машины М. Будем записывать индексы в строку после с или д,представляя их в двоичной системе счисления (например, св — — с110). Программу машины М будем записывать в виде последовательности всех ее команд с;д. — ~ сьд„Т, разделенных точкои с запятой. Тогда программа любой машины будет представлять собой слово в алфавите Р = (Л, ~,с,д,0,1,— +,В,Ь,Я,;).

Теорема 4.1. Существует алгоритпм нумераиии всех машин Тьюринга из указанного выше семейства такой, что для восстпановленшт программы по ее номеру также существует алгоритм.

Доказательство. Будем считать, что символы алфавита Р упорядочены (например, так, как это сделано выше). Тогда все слова одной длины Й можно упорядочить лексиграфически (как в словаре). Будем теперь просматривать все слова в алфавите Р в соответствии с их длиной: сначала длины 1, затем длины 2 и т.д. Слова одной длины й просматриваем в лексикографическом порядке. Для каждого слова применяем алгоритм, который проверяет, является ли это слово правильно построенной программой некоторой детерминированнои машины Тьюринга. Если да, то приписываем этой программе очереднои номер (начиная с О). При этом любой машине Тьюринга (из рассматриваемого семейства) по ее программе будет (алгоритмично) сопоставляться некоторый номер. Тот же перебор осуществляем, если задан номер и требуется найти соответствующую этому номеру программу.

Зафиксируем далее некоторую нумерацию машин Тьюринга т + — + М;, удовлетворяющую теореме. Так как машина М; вычисляет некоторую функцию ~(х), то мы получаем также некоторую нумера-

34

35

Распознанный текст из изображения:

цию всех вычислимых функций одной переменной г — ~ д(х). Заметим, что при этом может быть у,(х):— <р (х) при г ф 7', поскольку разные машины Тьюринга могут вычислять одну и ту же функцию ~(х).

Докажем теперь теорЕмы о том, что существуют сколь угодно сложно вычислимые функции.

Теорема 4.2. Для любой общерекурсивной функции Т(х) существует общерекурсивная функция ~(х), принимающая только 2 значения О и 1 и такая, что для любой машины Тьюринга М;, вычисля7ощей ~(х), хотя бы при одном х выполняется неравенство 1;(х) > Т(х), где ~;(х) — время работы машины М, на входе х ~точнее, на коде числа х).

Замечание. Отметим, что функция Т(х) может расти очень быстро. Например, функции д1(п) = и, д3(п) = п", д3(п) = пд'~"~, ..., д,„+1(п) = пд ~"~, ... общерекурсивны. Также общерекурсивна и функция п(п) = д„(п), которая растет с астрономической скоростью.

Доказательстпво. Для всех з б Я+ и х Е Я+ пусть Ц(х) обозначает время работы машины с номером г', если входом является код числа х ($,(х) может быть и бесконечным), и пусть щ(х) обозначает функцию, вычисляемую машиной М;. Определим функцию Дх) следующим образом:

1, если 1~(х) < Т(х) и р,(х) = О, Дх) =

О, иначе. Утверждение. Функция ~(х) — вычислимая, а следовательно, обще- рекурсивная.

Доказательство. Опишем алгоритм вычисления ~(х). По заданному х Е 2+ находим программу машины М (см. теорему 4.1), Вычисляем Т(х) (так как Т(х) — общерекурсивна, то для этого существует алгоритм). Имея программу машины М,, моделируем ее работу в течение Т(х) тактов, взяв в качестве входного слова код числа х. Если за Т(х) тактов машина остановится и результатом будет код числа О,то выдаем ответ 1, иначе выдаем ответ О. Моделируя работу машины, мы можем работать только с той частью ленты, на которой записывается входное слово, а также которая посещается головкой во время работы. Тогда на каждом шаге нам достаточно хранить лишь конечный кусок ленты, что позволяет определить содержимое ленты и после останова машины. Следовательно, весь процесс вычисления Д(х) алгоритмичен. В соответствии с тезисом Тьюринга существует машина Тьюринга, которая вычисляет ~(х). Мы примем здесь это утверждение, хотя для

описанной функции ~(х) можно и явно построить вычисляющую ее машину Тьюринга (правда, долго и громоздко).

Пусть машина М, вычисляет ~(х), то есть ~(х) = ~р;(х). В частности ~р,(г) = ~(з) и значит определено. Допустим, что 1;(г) < Т(з). Тогда по определению ~(х) получаем: если <р;(з) = О, то Дг) = 1, а если <р;(~) ф О, то ~(г) = О. В любом случае Дг) ф. ~р,(7) — противоречие. Следовательно (от противного) 1;(7,) > Т(г). Теорема доказана.

Теорема 4.3. Для любой общерекурсивной функции Т(х) существует общерекурсивная функция ~(х), принимающая только 2 значения О и 1 и такая, что для любой машины Тьюринга. М;, вычисляющей 7 (х), существует бесконечное число значений х, для которых выполняется неравенство Ц(х) > Т(х). Доказательство. Пусть д(х) = х — (~/х~) . Тогда функ-

2 ция д(х) вычислима и всюду определена (то есть общерекурсивна). При х =- О, 1, 2, 3,... функция д(х) принимает значения О, О, 1, 2, О, 1, 2, 3, 4, О, 1,.... Легко доказать, что функция д(х) принимает каждое значение из Л+ бесконечное число раз. Определим функцию ~(х) следующим образом: ~(х) = 1, если йд~,.~(х) < Т(х) и срд~,~(х) = О, О, иначе. Тогда функция ~(х) общерекурсивна (доказывается так же, как в предыдущей теореме). Пусть машина М, вычисляет Д(х), то есть ~(х) = <р,(х). Пусть 7' - любое число, такое, что д® = г (таких 7 бесконечно много). Допустим, что ~;(7) < Т®. Тогда по определению Д(х) получаем: если у;® = О, то ~® = 1, а если у,® ф О, то ~(~) = О. В любом случае Я) ф ~р,(у) - противоречие. Следовательно, Ц(~) > Т(~). Теорема доказана.

Справедливо еще более сильное утверждение, которое мы приведем без доказательства.

Теорема 4.4. Для любой общерекурсивной функции Т(х) существует общерекурсивная функция Дх), принимающая только 2 значения О и 1 и такая, что для любой машины Тьюринга М;, вычисляющей ~(х), множество тех х, для которых 1;(х) < Т(х), конечно.

Теоремы 4.2-4.4 показывают, что существуют сколь угодно сложно вычислимые общерекурсивные функции с двумя значениями (или, что эквивалентно, сколь угодно сложно распознаваемые языки). Возникает вопрос: а какой вообще может быть сложность задач (языков)? Существенный ответ на этот вопрос дает следующая теорема, которую мы приводим без доказательства.

36

37

Распознанный текст из изображения:

Теорема 4.5. Пусть общерекурсивные функции 1(п) и Т(и) таковы, что,, -+ оо при п -+ оо. Тогда сущестпвуетп язык

Т(о)

Ф о)доя~ 8 а

д', который распознаетпся некоторой машиной Тьюринга с числом шагов не более Т(и) ~для всех входных слов любой длины п) и не распознается никакой машиной Тьюринга с числом шагов 1(п).

Эта теорема показывает, что возможные функции сложности языков образуют довольно плотное множество. Можно ли получить результат о большей плотности, в общем случае неизвестно. Однако для одного важного интервала мы получим отрицательный ответ в п.

4.4. А именно, мы покажем, что не существует языков со сложностью распознавания (на машине Тьюринга) по порядку между и и п 1оя и.

4.3. Метод следов. Распознавание симметрии

Хотя в предыдущем параграфе показано, что существуют сколь угодно сложные задачи, получить высокую нижнюю оценку сложности для конкретной задачи очень тяжело. Один из методов для получения нижних оценок сложности решения задач на машинах Тьюринга, называемый методом следов, предложил Я. М. Барздинь, который впервые применил этот метод для оценки сложности распознавания симметрии на машине Тьюринга 15].

Определение. Рассмотрим точку на ленте машины Тьюринга между ячейками с номерами д и г+ 1. Следом в этой точке при работе машины на некотором входном слове будем называть последовательность всех состояний, в которые переходит машина, когда ее головка смещается из ячейки д в ячейку д + 1 или наоборот (то есть проходит над этой точкой). Пусть а = ада2 — входное слово. Тогда через чм(ад)а2) будем обозначать след машины М при работе на слове адах в точке, разделяющей ад и ао (считаем, что начальная конфигурация стандартная) .

Основная идея Барздиня состоит в использовании следующего утверждения.

Лемма 4.1. Пустиь ~м(ад~а2) = ~м(Ьд~62). Тогда при работе на входном слове ад6я машина М слева от точки, разделяющей ад и Ьо, работает так же, как на соответпствующей части при входном слове ада2, а справа так же, как на соответствующей частпи ири входном слове ЬдЬ2, причем ~м(ад)Ь2) = ~ддт(ад~а2) = ~м(Ьд~Ь~).

Доказательство. Пусть ~м(ад)а2) = ~м(Ьд)Ьз) = д;,д„...д;„, а ~м(ад~62) = д,,дд,...д„. Заметим, что работа машины М на слове адЬз слева от разделяющей точки однозначно определяется словом ад

и состояниями д,д,д,..., в которых головка переходит черз разделяющие точки влево, а работа справа от разделяющей точки однозначно определяется словом 6о и состояниями д,д,д,..., в которых головка переходит через разделяющие точки вправо. Переход головки машины М через соответствующие разделяющие точки делит работу М на каждом из слов ад)62, ад)а2 и бд~62 на этапы. Машина М на первом этапе на слове адЬо работает так же, как на первом этапе на слове ада2. Поэтому д, = д,, и машина М на втором этапе на слове ад62 работает так же, как на втором этапе на слове 6д62. Отсюда д; = д;, и машина М на третьем этапе на слове адЬо работает так же, как на третьем этапе на слове ада2. Продолжая это рассуждение, мы получаем утверждение

леммы.

Определение. Пусть А = (0,1) и слово а = адаз...а„Е А*. Будем говорить, что слово а симметрично, если ад —— а, ая — — а,„д и т.д. Пусть машина Тьюринга М имеет ленточный алфавит С и множество состояний ф, причем А С С и д' Е Я, д" Е Я. Будем говорить, что М распознает симметрию, если для любого входного слова а б А* машина М всегда останавливается и при этом находится в состоянии д', если а симметрично, или д", если а не симметрично.

,У тверждение. Существ ует машина Тьюринга М, котпорая распознастп симметрию и делает ири любом входном слове длины п не более си шагов, где с — некитпорая константа.

2

доказательство. Достаточно построить машину М, которая запоминает и стирает первый символ, перегоняет головку в конец слова и сравнивает символ в памяти с последним символом слова. Если они не совпадают,то М переходит в состояние д" и останавливается. Если совпадают, то она стирает последний символ, возвращается в начало слова и повторяет процесс. Если слово полностью стерто, то М переходит в состояние д' и останавливается. При этом головка не более и раз пробегает по слову длины не более п, Поэтому общее число шагов есть 0(п2).

Определение. Пусть 5(п) — число всех симметричных двоичных слов длины п, а Е(п) — число всех симметричных двоичных слов длины и, удовлетворяющих некоторому заданному свойству Е. Будем говорить, что свойство Е выполняется для почти всех симметричных слов, если 1пп„, — „= 1.

Е(п)

Лемма 4,2. Число различных двоичных симметричных слов длины п равно Я(и) = 2) '21.

Это утверждение следует из того, что симметричное слово одно-

39

Распознанный текст из изображения:

~Атг(г) ~ ( 2) г1 — г+сгг1окг т

~Дгг~ < (и, 8)2гг(4+с1окгт)

~Агг(2)~ < 2Гг1 141+стг1оКг т

~А"(4,~)) < 2Гг1-г

Поэтому

Ф,"!

]1ш см — О

-+с 2Гг1

~А"(г,~)~ < 2Г 1 '.

~ дгг)

с ~ ( ( + 8)2гг( — 4+с1оКг т) 2Гг1

4О

41

значно определяется своей первой половиной.

Теорема 4.6 (Я. М. Барздинь). Для любой машины Тьюринга М, распознающей симметрию, существует константа см > О, такая, что для почти всех симметричных слов Х время 1м(Х) работы машины М на слове Х удовлетворяет неравенству Фм(Х) > см~Х~~, где ~Х~ — длина слова Х.

Доказательство. Пусть М вЂ” далее некоторая фиксированная машина Тьюринга, распознающая симметрию двоичных слов.

Лемма 4.3. Пусть М распознает симметриюг агаг и Ь162 — симметричные слова и ~м(а1~аз) = ~м(61~ЬК). Тогда аг62 — симметричное слово.

Доказательство. Так как М распознает симметрию, то при работе на словах а1 а2 и 61Ь2 она остановится в состоянии д' ("да"), а при работе на слове агЬо она также обязательно остановится в некотором состоянии. Но тогда из леммы 4.1 следует, что и при работе на слове а16к она остановится в состоянии ц' ("да"). Так как М распознает симметрию, то это означает, что аг62 — симметричное слово. Лемма доказана.

Определение. Пусть а = а1а2 и пусть ~а1~ = г ((а) — длина слова а). Тогда через ~,'д(а) будем обозначать ~м(а~~а2). Пусть © = (д1, дг,..., дт) — множество всех состояний машины М. Пусть 1 ( г ( и и Ч Е Я* (~ — слово в алфавите ф. Через А" (~, г) будем обозначать множество всех симметричных двоичных слов а длины п, таких, что

См(а) = 6.

Лемма 4.4. Длх любого г', тпакого, что 1 < г ( Я~, и длх любого ~ б ~* выполнхетсх неравенство:

Доказательство. Пусть а Е А"(4,~), Ь Е А"(г,~), а = а1а2, Ь = Ь1Ь2 и ~а1 ~ = ~Ь~~ = г. Тогда слова а и 6 симметричны и ~м(а1)а2) = ~м(61 ~6з). По лемме 4.3 отсюда следует, что слово а~Ь2 тоже симметрично. Поскольку оба слова а162 и 616о симметричны и )а1) = ~61 ~ < Д~, то а1 = 61. Следовательно, у всех слов из А" (г, ~) одинаковое начало длины г. Поскольку симметричные слова однозначно определяются своими первыми ф буквами, то

Лемма 4.5. Пусть (,'? = ~д1,д2,...,д„) — алфавит, в котором

г > 2. Тогда количество различных слов длины не более а' в алфавите

Я не превосходитп т"+1.

Доказательство. Число таких слов равно т+ т + т~+ . + т" = " < т~+ .

т-1

Определение. Пусть с = сопв1 > О. Через А",(г) будем обозначать множество всех симметричных двоичных слов а длины п, таких, что длина следа ~Я~(а) ~ < ~сп~.

Лемма 4.6. Если машина М имеет г состохний, то длх любого г, такого, что 1 < г ( ф, выполнхетсх неравенство:

Доказательство. Из лемм 4.4 и 4.5 получаем

~А~~(4)~ ( ~ ~А~(~ ~) ~ < 2(г ' . гс" . 2Гг1 ~+сг оКгт й6<( !

Определение. Пусть с = сопят > О. Через В," будем обозначать

множество всех симметричных двоичных слов а длины и, таких, что

~Я~(а) ~ < ~сп) хотя бы для одного г такого, что ( 4) < г ( ф. Лемма 4.7.

Доказательство. Согласно лемме 4.6 для любого г, такого, что

Г4) < ю < ~~~, выполняется неравенство:

фгг~ < ( ~ ~ + 1)2Гг1 — Д1+сп1оКгт (

с

< ( — + 2)24+сг~1оКгт+2 (и+ 8)2'г(4+с!оКгт)

4

Лемма 4.8. Существует константа см > О, таках, что

Доказательство. Согласно лемме 4.7,

Распознанный текст из изображения:

Поэтому утверждение леммы 4.8 будет выполняться для любой константы с <

41ок~1

Продолжим доказательство теоремы Барздиня. Выберем для данной машины М константу см, удовлетворяющую условию леммы 4.8. Пусть Р, "— множество всех симметричных двоичных слов, не входящих в В,". По леммам 4.2 и 4.8 имеем

поэтому почти все симметричные двоичные слова входят в Р" . При

см'

этом для любого а Е Р, и любого т, такого, что ~4~ < т < Д~,

выполняется неравенство ~~~ (а) > ~си~. Так как время работы машины

Тьюринга не меньше, чем длина всех следов, то для всех слов а б Р,"

имеем:

п и см

1м(а,) > (~ —,~ — ~ — /) ~сми~ > — и

2' 4 8

при достаточно больших и. Теорема 4.6 доказана.

4.4. Регулярные языки

Регулярные языки — это языки, распознаваемые автоматами. В этом контексте автомат можно определить как машину Тьюринга со следующими ограничениями: головка машины на каждом шаге движется вправо или машина останавливается; машина останавливается тогда и только тогда, когда головка обозревает символ Л; машина останавливается в одном из двух состояний д ("принять") или д" ("отвергнуть").

Определение. Пусть С вЂ” ленточный алфавит автомата М и А = СЦЛ1. Пусть 1 С А*. Будем говорить, что автомат М распознает язык Ь, если для любого слова а Е А* работа М при входном слове а (в стандартной начальной конфигурации) заканчивается состоянием а, если а Е Ь, и заканчивается состоянием д, если а ~ Ь.

Определение. Пусть А — некоторый алфавит и Л С А'— некоторый язык в алфавите А. Для каждого слова а е А* остаточный язык Ь; определим следующим образом

Язык называется регулярным, если у него лишь конечное число различных остаточных языков. (Здесь рассматривается и 6 = Л вЂ” пустое слово; при этом Л б Ь; ~=» а Е Ь).

В теории автоматов и языков доказывается следующая теорема (см., например, [1Ц).

Теорема 4.7. 1) Язык, распознаваемый любым автоматпом, регулярен. 2) Для любого регулярного языка существует распознающий его автомат.

Следствие. Если язык Ь регулярен, тпо для него существувтп распознающая его машина Тьюринга, время работы котпорой (число шагов) на каждом входном слове длины и равно п+ 1.

Оказывается, что не существует языков, для распознавания которых на машинах Тьюринга достаточно времени существенно меньшего, чем и 1оя2 и (и — длина входного слова) и не достаточно времени п+ 1. Более точно это выражается в приводимых ниже теоремах.

Теорема 4.8. Пустпь машина Тьюринга М распознает язык Е ~ А'* и пусть сущсствувтп кнстанта с > О такая, что при работе М на любом входном слове а Е А* длина следа ~м(а) (см. стр. 38) не превосходит с для всех 1 ( т' ( и, где и — длина слова а. Тогда 1' — регулярный язык. (Следовательно, существуетп автпоматп, распознающий Ь с с = 1).

Доказательство. Пусть а е А*. Построим множество Р, -всех следов, которые могут получиться при работе М на словах вида ах е А* в то~ке 3, разделяющей а и х. Пусть след а,,а1,а,,... 5, ~ Ц-,. Рассмотрим работу машины М слева от разделяющей точки. Она однозначно определяется словом а и теми состояниями д;„д;„..., в которых находится машина, когда головка возвращается на левую зону через точку т. По условию в ( с. Если в четно, то машина останавливается слева от точки т. В этом случае к последовательности д;,д;,д;, припишем +, если М останавливается в состоянии "принять", и припишем —, если М останавливается в состоянии "отвергнуть". Так как в < с, то возможных следов конечное число и разных возможных множеств .Рв также конечное число. Тогда утверждение теоремы 4.8 вытекает из следующей леммы.

Лемма 4.9. Если Рв — — Р~, то остаточные языки Ьв и Хь совпадают.

Доказательство. Пусть х — любое слово из А*. Рассмотрим работу М на словах ах и 6х. Пусть д,,д;,д;,... а,, и д~,д~,... д~„— следы в точках, разделяющих а и х, 6 и х. Заметим, что работа справа от разделяющих точек однозначно определяется словом х и состояниями д;,а;,Ч;,... и дт,а;,а;,..., в которых головка переходит через разделяющие точки вправо. При этом а,, и д, однозначно определяются по а и

42

Распознанный текст из изображения:

6. Так как Рв — — Рь, то о;, = д,, и работа справа после первого перехода через разделяющие точки происходит одинаково. Тогда д;, = д, Опять, так как Рв — — Рь, то д;, = д, и опять работа справа происходит одинаково. Последовательно получаем, что в = т и д;„ = о, для всех т = 1,2,...,в. Если в нечетно, то после перехода вправо в состоянии д;, в обоих случаях работа справа будет одинаковой и, следовательно, М остановится в одном и том же состоянии. Если в четно, то машина в обоих случаях остановится слева от разделяющей точки, причем в одном и том же состоянии, поскольку Рв — — Р~ и след о, д;,... о;, в обоих множествах дополнен одним и тем же знаком + или —. Таким образом, М принимает слово ах тогда и только тогда, когда она принимает слово Ьх, то есть либо оба слова входят в Ь, либо оба не входят в Х. Поэтому Х; = Ц. Этим доказана лемма, а вместе с ней и теорема 4.8.

Докажем теперь несколько лемм, которые используем в следующей теореме.

Лемма 4.10. Пусть А = 1а1, а2,..., а„~ — алфавит, 61,62,...,6„ — разные слова в этом алфавите, 1; — длина слова 6; и 1„, = шах, 1,. Тогда 1 „> с1оя~п, где с > Π— некоторая константа, зависящая только от г.

Доказательство. Лемма очевидно выполняется при г = 1, Пусть г > 2. Все п слов имеют длину, не превосходящую 1 „. Но всего таких слов не больше, чем т' '*+' (см. лемму 4.5). Поэтому и < т' *+', 1,„„) 1ок„п — 1 > с1 1одп = 1-,~-„- 1окз и. Лемма доказана.

Лемма 4.11. При условиях леммы существует константа с > О такая, что ~;," 11; > сп1оя2п.

Доказательство. Лемма очевидно выполняется при т = 1. Пусть т > 2. Число всех слов длины меньшей, чем 12 1о~„п~ не превосходит

— "!о о — '1о в

г "2~'я""1 < г2 1оя"" = ~/й. Поэтому среди слов 6; не менее, чем и — ~/й слов, имеют длину не меньше чем Д 1он„п~. Поэтому

1

1, ~~ (и — ~/и) ~ — 105„п! ~~ сп 1ояз и

2

для некоторой константы с.

Лемма 4.12. Пусть числовая последовательность п1, п2,..., пь,... не ограничена сверху, Тогда из нее можно выделить подпоследовательность и;„п;„... такую, что для любого в и всех 1 < ~ < з, выполняется и, < и;,.

Доказательство. Первым элементом подпоследовательности возьмем п1. Пусть уже выбраны и;„и,„..., и;„. Тогда, просматривая

элементы по порядку после и;, в качестве очередного элемента выбираем первый элемент и;„„больший, чем и;„. Поскольку и;„, > и;„а все элементы между и;„и и;, не превосходят и;„, то все они меньше, чем и„. Поэтому, если все элементы и; исходной последовательности с ~ = 1,2,...,г, — 1 меньше, чем п,„то все элементы и с ~ = 1,2,...,г„+1 — 1 меньше, чем и,,+, Таким образом по индукции проверяется требуемое свойство. То, что и;, существует, следует из неограниченности исходной последовательности.

Обозначим через ~м(а~Ь) след при работе машины Тьюринга М на слове а6 в точке, разделяющей а и 6.

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

Утверждение этой леммы вытекает из леммы 4.1.

При работе машины Тьюринга на входном слове а = а1а2... а„ точкой г будем называть точку после ячейки, в которой находится а;.

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

Доказательство теоремы (от противного). Допустим, что Х не регулярный язык. Тогда по теореме 4.8 Им(п) неограниченная последовательность. По лемме 4.12 из нее можно выделить подпоследова-

тельность п1, п2,... такую, что

(4.1)

с1м(п) < о,,~(п,)

для всех п < и, (г = 1, 2,...).

Лемма 4.14. Пусть п1, п~,... удовлетворяют (4.1) и а; — слово длины и;, на котором достигаетсх с~м(п;). Тогда при работе М на слове а, один и тот же след в точках 1, 2,..., и, не может повторяться более чем 2 раза.

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

44

Распознанный текст из изображения:

доказана.

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

Следствие. Если Ыу(п) = о(1оки) или Тщ(п) = о(п1ояп), то существует машина Тьюринеа (автомат) Ф, распознающая тот же язык Ь, для которой Ну(п) = 1, Ту(п) = п+ 1.

4.5. Классы Р и УР

Определение. Пусть алгоритм осуществляет преобразование «р . А* -+ В* слов в алфавите А в слова в алфавите В. Тогда этот алгоритм называется полиномиальным (или имеющим полиномиальную сложность), если существует полином р(п) такой, что для любого натурального и время работы алгоритма на любом входном слове длины п не превосходит р(п). (При этом можно считать, что все коэффициенты в р(п) неотрицательны, то есть р(п) возрастающая функция.)

Определение. Задачей распознавания называется любое отображение «р: А* -+ ("да", "нет").

С любой задачей распознавания «р можно связать язык Ь, С А* следующим образом: а «= Ь, ~=: «р: а -+ "да". И обратно, любой язык можно рассматривать как задачу распознавания.

Определение. Класс Р— это класс всех языков (задач распознавания), для каждого из которых существует распознающий алгоритм с полиномиальной сложностью.

Определение. Будем говорить, что язык Ь, С А* полиномиально сводится к языку Л2 С В', если существует полиномиальный алгоритм (например, машина Тьюринга) «о: А' ~ В*, такой что «р(а) (= Ь2 <=~ а Е.«1.

Теорема 4.10. Пусть Е1 С А*, Е2 С В*, Ез «= Р и Л1 полиномиально сводится к Ь2. Тогда Ь1 Е Р.

Доказательство. По условию существуют машины Тьюринга М1 и М2 такие, что М1 полиномиально сводит «1 к Ьз, а Мя с полиномиальной сложностью распознает Ь2. Рассмотрим машину Тьюринга М = М2(М1). Тогда М: А* -+ ("да", "нет"), причем для любого слова

а Е А* имеем М(а) = "да" с=~ М2(М1(а)) = "да" с=> М1(а) е Ьг с=~ а е Ь1,

то есть М распознает язык Л1. По условию время работы (число шагов) машин М1 и Мз на входных словах длины п не превосходит р1(п) и р2(и), где р1, р2 — полиномы. Тогда время работы М на слове а длины п не превосходит р1(и) + рз(!М1(а) !), где !М1(а) ! — длина слова М1(а). Так как машина Тьюринга М1 на каждом шаге может увеличивать длину слова не более чем на 1, то !М1(а)! < и+ р1(п) и время работы М на а не превосходит р1(п) + р2(п + р1(п)) = рз(п), где рз — поливом. (Здесь считается, что все коэффициенты в р2 неотрицательны и, следовательно, р2(и) — неубывающая функция). Таким образом М распознает язык Ь1 с полиномиальной сложностью. Теорема доказана.

Эта теорема позволяет получать полиномиальные алгоритмы для одних задач распознавания из имеющихся полиномиальных алгоритмов для других задач просто путем полиномиального сведения одних задач к другим.

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

Определение. Язык Ь С А (задача распознавания) входит в класс МР, если и только если существуют алфавит В, полином д(п) и предикат Ц(х, у): А* х В* -+ ("истина", "ложь") такие, что Ч(х, у) е Р и для любого слова а Е А* выполняется:

а е Ь <=~ ЛЬ «= В (!Ь! < д(!а!)Йфа, Ь))

(здесь !а! и !Ь! — длина слов а и Ь).

Слово Ь называют сертификатом для слова а, а алгоритм, распознающий предикат фа, Ь), — алгоритмом проверки сертификата. Таким образом, если а б Ь (в задаче распознавания для входа а ответ "да"), то должно существовать быстрое подтверждение для этого, то есть должен существовать подтверждающий это сертификат Ь (небольшой длины) и быстрый способ подтвердить, что это действительно подходящий сертификат. Если же а ф Ь, то такого Ь просто не должно существовать. Таким образом, ответы "да" и "нет" здесь не симметричны. Заметим также, что для случая а Е Л лишь утверждается существование сертификата Ь, но ничего не говорится о сложности его нахождения (если в В имеется т. букв и !а! = и, то !Ь! < д(и) и число таких слов Ь не меньше, чем т«««"~«, то есть экспоненциально зависит от

Распознанный текст из изображения:

Рассмотрим примеры языков из 1ЧР.

КЛИКА. Вход: любой неориентированный граф С [7~ и натуральное число й.

Воирос: Существует ли в графе С клика размера к, то есть к вершин таких, что любая пара из них соединена ребром?

Более строго, мы должны задать входной алфавит А и способ представления графов и числа й в этом алфавите. Можно, например, считать, что А = (0,1,;) и граф задается матрицей смежности (из 0 и 1), которая затем выписывается в одно слово подряд по строкам матрицы с разделителем; между строками матрицы. В конце после; записывается Й в двоичной системе.

Утверждение. КЛИКА е ЮР.

Доказательство. В качестве сертификата Ь для входа а будем брать список из номеров й вершин, составляющих клику. Очевидно, ~6~ < д(~а~), где д — некоторый полином. Предикат Я будет обозначать, что данные вершины задают клику в данном графе и этих вершин ровно Й. Для распознавания справедливости такого свойства © легко построить алгоритм со сложностью, не превосходящей полинома от суммарной длины кода графа а и сертификата Ь.

ГАМИЛЬТОНОВ ЦИКЛ (ГЦ). Вход: любой неориентированный граф С.

Вопрос: Существует ли в графе С гамильтонов цикл, то есть цикл, проходящий через каждую вершину ровно 1 раз?

Утверждение. ГЦ е ИР.

Доказательство. Сертификатом здесь является последовательность из вершин ю1,ю2,..., о . Предикат Я выражает утверждение, что в этой последовательности все вершины графа встречаются ровно 1 раз и в графе есть ребра (в;, ю;+1) для всех г = 1, 2,..., т — 1, а также ребро (и,„, и1). Для распознавания справедливости такого свойства Я легко построить алгоритм со сложностью, не превосходящей полинома от суммарной длины кода графа а и сертификата 6.

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

ВЫПОЛНИМОСТЬ (ВЫП). Вход: любая формула Г в виде КНФ.

Вопрос: существует ли набор переменных (а1,..., и„„), на котором Г(а1,..., о ) = 1 (выполнима ли г )?

Утверждение. ВЫП Е ИР.

Доказательство. Сертификатом для входа Г является набор (а1,..., а~), на котором Р(а1,..., а ) = 1. Предикат Я выражает тот факт, что данная формула Е на данном наборе (а1,..., а~) действительно принимает значение 1. Для распознавания справедливости такого свойства Я легко построить алгоритм со сложностью, не превосходящей полинома от суммарной длины кода формулы Г и кода набора (а1,..., а,„).

Еще раз обсудим вопрос о представлении входных данных. Мы не можем, например, включить в алфавит А произвольные переменные, так как их бесконечное число, а любая машина Тьюринга работает лишь с конечными алфавитами. Однако достаточно взять алфавит А = (х, О, 1, Й, Ч, ~, (, )) и переменную х; записывать как х с идущим далее числом г', представленным в двоичной системе счисления. Обратим также внимание на то, что в определении задач распознавания на вход может поступить любое слово в заданном алфавите А. В задаче ВЫП многие такие слова не представляют КНФ. Предполагается, что ответом для таких входных слов является "нет". Аналогично понимаются и другие задачи (например, КЛИКА или ГЦ).

Теорема 4.11. Р С ИР.

Доказательство. Пусть Ь Е Р, и Ь С А*. Возьмем любой алфавит В и д(п) = 1. Предикат Я(а, 6) пусть выражает тот факт, что а е Ь (независимо от Ь). Так как Х е Р, то предикат Я распознается за время, полиномиально зависящее от ~а~, а значит и от ~а) + ~д), то есть Я б Р. При этом, очевидно, что для любого а Е А* справедливо соотношение

а Е Ь <=~ ЗЬ б В (~Ь| < ЖЯ(а, Ь))

(сертификат 6 здесь не зависит от а). Таким образом, А Е ИР. Теорема

доказана.

4.6. Теорема Кука

Определение. Язык Ь (задача распознавания) называется

МР-трудным, если любой язык А1 из МР полиномиально сводится к

Ь.

В соответствии с теоремой 4.10, если язык Ь является УР-трудным и Ь Е Р, то ХР С Р и, с учетом теоремы 4.11, Р = ЫР. И обратно, если Р ф ЖР, то Ь ~ Р. Таким образом, ФР-трудность

48

49

Распознанный текст из изображения:

языка является косвенным свидетельством того, что Ь ф Р (косвенным потому, что вероятно Р ф ИР, но это пока не доказано и не опровергнуто).

Определение. Язык Ь (задача распознавания) называется ФР-полным, если Л е ХР и Ь является ИР-трудным.

Естественно возникает вопрос о том, существуют ли такие "универсальные" задачи в классе ИР, к которым полиномиально сводятся все задачи из МР. Оказывается, что существуют. Первый результат такого рода был установлен С. Куком [12].

Теорема 4.12 (С. Кук). Задача ВЫП (о выполнимости КНФ) яваяется НР-полной.

Дпказатвльство. Выше уже доказано, что ВЫП Е ЖР. Поэтому надо доказать, что любой язык А из ИР полиномиально сводится к ВЫП. Пусть 1 ~ МР и Ь С А*. Это означает, что существуют полипом д(п), алфавит В и предикат Я(х, у): А* х В* — э (" истина", "ложь") такие, что фх, у) Е Р и для любого слова а Е А* справедливо

а ~= Ь ~=» ЭЬ(~Ь~ < д(~а])Щ(а, Ь)).

Нам надо показать, что Х полиномиально сводится к ВЫП. Это означает, что надо построить такое преобразование с полиномиальной сложностью ~р: А* — ~ С*, где С вЂ” алфавит задачи ВЫП, что а Е Ь «=» <р(а) = Ра — выполнимая КНФ от некоторых переменных.

Так как фх, у) Е Р, то существует машина Тьюринга М, которая распознает предикат фх, у) за время (число шагов), не превосходящее некоторого полинома р0 от длины входа. Будем считать, что начальная конфигурация машины М~ является стандартной, то есть пара (а, 6) представляется на ленте двумя словами а и Ь с одной разделяющей ячейкой, в которой ставится пустой символ Л, головка обозревает самый левый символ слова а и машина находится в начальном состоянии д~. Тогда время работы М~ на произвольной паре (а,6) не превьппает р00а~+]Ь|+1). Будем считать, что машина М~ останавливается только в одном из двух заключительных состояний, причем заключительное состояние д0 машины М~ соответствует ответу "да" (какое состояние соответствует ответу "нет" для нас будет не важно).

Пусть дано а б А* и ]а] = и. Тот факт, что а (= Ь, равносилен в соответствии с (4.2) тому, что найдется слово Ь Е В* с длиной ~6] < д(и) такое, что машина М~, начав работу на паре (а, 6), придет в состояние д0 —— "да". При этом время работы М~ на паре (а, 6) не превосходит ро(и + д(п) + 1) = р(и), где р — некоторый полином. Отметим, что

можно считать, что во всех полиномах все коэффициенты неотрицательны. Тогда р(и) > п+ 1+ д(п).

Несколько модифицируем программу машины М~. А именно ес)

ли машина М~ находится в некотором заключительном состоянии и головка обозревает некоторый символ, то пусть машина М~ оставляет в ячейке тот же символ, головка никуда не сдвигается и машина остается в том же состоянии. То есть реально ничего не происходит, но формально машина продолжает работать бесконечно. Полученную машину обозначим М. Тогда для слова а Е А* длины ~а~ = п имеем:

а Е Е «=» ЗЬ Е В*(~Ь| < д(п) и машина М,

запущенная на паре (а, 6), в момент времени р(п)

будет находиться в состоянии дв = "да").

(4.2)

Наша дальнейшая цель — записать правую часть в этой равносильности в виде КНФ Р,-(х~,..., х, ) от некоторых переменных, так чтобы формула Ра была выполнима тогда и только тогда, когда эта правая часть истинна. Перепишем (4.2) более подробно:

а Е Ь вЂ”. ЗЬ (= В*ОКО, К~,..., Кр<„~ (~Ь! ~ ~д(п) и

Кв, К~,..., Кр~„~ — конфигурации машины М такие,

что Ко — начальная конфигурация для пары (а, 6),

состояние в К ~„~ есть дв и для каждого

~ = О, 1,...,р(п) — 1 конфигурация К+~ получается

из К по программе машины М).

(4.3)

Пусть ячейки ленты в М занумерованы целыми числами слева направо и ячейка, с которой головка начинает работать (и с которой начинается слово а), имеет номер О. Тогда за р(и) тактов головка не может попасть в ячейки с номерами меньше — р(и) и больше р(и). Поэтому можно считать, что конфигурации К0, К~,..., Кр~„~ определены только на зоне ~ — р(п), р(и)] ленты.

Пусть машина М имеет ленточный алфавит Р = 1а0, д~,..., с~ ), где Нв = Л, при этом А С Р и В С Р. Пусть И' = (д0, д~,..., д~) — множество всех состояний машины М, причем д~ — начальное состояние и д0 = "да". Введем булевские переменные х,'.~,у!,~„', где г = — р(п),— р(и) + 1,...,р(и);7' = 0,1,...,т;й = 0,1,...,1;~ О, 1,..., р(п) и придадим им следующий смысл:

х~~ = "истина" «=» в г-й ячейке в конфигурации К~ находится символ И.;

50

51

Распознанный текст из изображения:

можно выразить в виде КНФ Р4 длины не более р4(п), где р4

некоторый полином.

Доказательство. Этот факт выражается формулой

~+1 1+1 1+1

ч,р(з',м) ф(~д уч+щ,ь) )

~ я(~)-1у(~) (-~ ~ т ( ~+1

~=0 в= — р(~~) уа у=О ~1,д = *1,у

Первая часть этой формулы выражает изменение информации в обозреваемой ячейке, изменение состояния и сдвиг головки, вторая часть выражает тот факт, что символы во всех ячейках, кроме обозреваемой, не изменяются. Выражение в первой скобке в Г4 — это функция от 6 переменных и ее (как любую функцию алгебры логики, отличную от константы 1) можно представить в виде КНФ некоторой длины Ь1. Аналогично можно представить в виде КНФ константной длины Ьз функцию от 2т+ 1 переменных, стоящую во второй скобке. При этом Г4 преобразуется в КНФ К4 длины р(п) . (2р(п) + 1) т . 1 . Ь1 + р(п) ° (2р(п) + 1) - Ь~ < р4(п), где р4 — некоторый полином.

Положим Г5 —— Р1 Г2 Гз Г4. Тогда Г5 — КНФ и по леммам 4.16-4.19 на наборе переменных х,', у,', ~~ она истинна тогда и только тогда, когда переменные корректно задают некоторое вычисление машины М, приводящее в состояние до — — "да", для входной пары (а, в), где 6 — какое-нибудь слово из В' такое, что ~Ь~ ( д(~а~). Таким образом Г; истинна хотя бы на одном наборе (т.е. выполнима) в том и только в том случае, если истинна правая часть в (4,3) и, следовательно, если а е Ь. Получаем, что Г; — искомая КНФ. Ее длина не превосходит некоторого полинома от и. При этом нетрудно понять, что по данному слову а (и фиксированной программе машины М) эта КНФ Р; = Р1 Рз. Гз Р4 выписывается за время, ограниченное полиномом от ее длины, и, следовательно, ограниченное полиномом от длины слова а. Таким образом, отображение а — ~ Га является полиномиальным сведением языка Ь к языку ВЫП. Поскольку Ь— произвольный язык из МР, то получаем, что ВЫП вЂ” МР-трудная задача, а так как ВЫП (= ИР (см. п. 4.5), то ВЫП вЂ” МР-полная задача. Теорема Кука доказана.

4.7. Сложность задач о выполнимости

Следующая теорема позволяет выводить ИР-полноту одних задач из ХР-полноты других задач.

Теорема 4.13. Если Ь1 — НР-трудный язык и Ь1 полиномиально сводится к языку Е~, то Ь2 — ИР-трудный язык. Если при этом 12 Е НР, то Л2 — ЮР-полный язык.

Доказательство. Пусть Ь вЂ” любой язык из 1ЧР. Так как Ь1 — МР-трудный язык, то Ь полиномиально сводится к Л1. При этом

1

если длина исходного слова равна п, то при сведении оно переходит в слово длины не более д(п), где д — некоторый полином. Так как по условию Ь1 сводится к Ь2 за время, полиномиально зависящее от длины сводимого слова, то композиция двух сведений полиномиально сводит Ь к Ь2. Так как А — произвольный язык из НР, то Х2 — МР-трудный язык по определению;

Определение. КНФ, у которой в каждом дизъюнкте ровно 3 различных литерала, будем называть З-КНФ.

Задача 3-выполнимость (З-ВЫП).

Входной алфавит тот- же, что и в задаче ВЫП.

Вопрос: верно ли, что входное слово — это З-КНФ, которая выполнима.

Утверждение. 3-ВЫП Е ЖР.

Доказательство. Задача 3-ВЫП удовлетворяет определению задач из класса ИР. При этом в качестве сертификата достаточно взять набор Ь, на котором данная 3-КНФ выполнима (если такой существует), а алгоритм проверки сертификата будет проверять, действительно ли входное слово есть 3-КНФ и верно ли, что эта КНФ на наборе й равна 1. Все это можно осуществить за полиномиальное (от длины входа) время.

Теорема 4.14. Задача 3-ВЫП МР-полна.

Доказательство. Сведем задачу ВЫП полиномиально к задаче 3-ВЫП. Пусть А — алфавит обеих задач. Нам надо для каждого слова а е А* за полиномиальное (от длины слова а) время построить слово у(а) так, чтобы ~р(а) было выполнимой 3-КНФ тогда и только тогда, когда а — выполнимая КНФ. Если а Е А* не КНФ, то положим у(а) = а. Если же а — КНФ Р1 Р2 -.... Р, от переменных х1, х2,..., х„, то преобразуем ее в 3-КНФ ~р(а) = Г1.Г2 ....Р, следующим образом. Пусть )" = (у1, уз,... ~ — некоторые переменные, которые не встречаются в КНФ а. Рассмотрим 4 случая.

1) Если Р; = 1,1ЧЦя Ч1;з, то положим Р; = Р,.

2) Если Р; = й,1~/8,2, то положим Г = (й,1Ч1,2Чу-) (й,1Чй;2~/у ), где у~ Е У. Заметим, что Г, = 1 с=» Р, = 1.

54

55

Распознанный текст из изображения:

3) Если Р, = 8,, то положим

г; = (г, ~ уь \~ ж) (г; ~ ук ~ й) . (~; Ч ут, ~~ уг) (г; ~ я Ч ую),

где у~ ф- уь Опять Г, = 1 ~=~ Р; = 1. 4) Пусть 0; = 1т Ч Фг Ч... Ч 1,„и т ) 4. Положим

Г = (~~ ~ ~г ~ У~)(У~ ~ ~з ~ Уг)(уг ~ « ~ Уз) .

(Ут — 4 ~ ~ш-г ~ Ут — з)(ут — 3 ~ ~т — 1 ~ ~па) ~

где все у различны.

Лемма 4.20. В случае ф, если Г, = 1, то и Р; = 1, а если Р; = 1, то существует набор значений переменных у~,уг,...,у„, з такой, что Х", = 1.

Доказательство. Пусть й = (а~,..., а„) — набор значений перемепных х~,..., х„из Р, и,В = (Д,...,,8 з) — набор значений переменных У1,..., Ут, з. Пусть Г,(а, ф) = 1, то есть все скобки в Г, на наборе (Й,Д) равны 1. Если Д = О, то й~(й) Ч йг(ст) = 1 и Р;(а) = 1. Если Д~, з =17 той,„1(а)М,„(а) = 1и0,(й) = 1. ЕслижеД = 1и,В з =О, то найдется Й такое, что Д = 1, Д+~ = О. Так как ДМт,+г(й) ~/Д+~ — — 1, то в этом случае 4+г(й) = 1 и Р;(а) = 1. Следовательно, если Г; = 1, то и Р, = 1. Обратно пусть Р,(й) = 1. Тогда существует 1~ такое, что ~~(Й) = 1. Если Й = 1 или Й = 2, то выберем Д =,ог =... —— ,В з = О. При этом Г;(6,~3) = 1. Если Й = т — 1 или Й = т, то выберем Д ~Вг ° ° ° — Дд — 3 — 1 ° При этом опять Х"; (а, ~9) = 1. В остальных случаяхположимД=Д=...=Д г — — 1,Д ~=Д=...=,В з=О. Снова получим Г;(а, ~3) = 1. Лемма доказана.

Проделаем указанные выше в пунктах 2)-4) замены Р; на Г;, используя для разных Р; разные переменные у . Тогда по лемме 4.20 получаем, что если 3-КНФ Г~. Гг ... Г, равна 1 на каком-то наборе, то на том же наборе равна 1 и КНФ Р~ . Рг ... Р„и обратно, если КНФ Р~ . Рг.... Р, равна 1 на некотором наборе, то существует набор, на котором 3-КНФ Г~ Гг -... Г, также равна 1. Таким образом 3-КНФ Р~. Гг .... Г, выполнима тогда и только тогда, когда выполнима КНФ Р~. Рг.... Р„то есть наше преобразование является сведением задачи ВЫП к задаче З-ВЫП.

Распознать, является ли входное слово а е А* КНФ можно за полиномиальное от длины а время. Преобразовать все Р; в Г; также можно за полиномиальное время. Поэтому мы имеем полиномиальное сведение задачи ВЫП к задаче 3-ВЫП. Поскольку задача ВЫП является МР-полной и 3-ВЫП Е НР, то по теореме 4.13 получаем, что задача 3-ВЫП является ХР-полной.

Посмотрим, нельзя ли в последней теореме заменить 3 на 2. Определение. КНФ, у которой в каждом дизъюнкте не более 2

литералов, будем называть 2-КНФ.

Задача 2-выполнимость (2-ВЫП).

Входной алфавит тот же, что и в задаче ВЫП.

Вопрос: верно ли, что входное слово — это 2-КНФ, которая выполнима.

Теорема 4.15. Для' задачи 2-ВЫП существует алгоритпм с полиномиальной сложностью (то есть 2-ВЫПе Р).

Доказательство. Проверить, является ли входное слово 2-КНФ, можно за полиномиальное время. Поэтому будем считать, что нам уже дана 2-КНФ Р~ Рг ... Р, и требуется выяснить, выполнима ли она.

11усть дизъюнкты Р' = х; Ч 1~ и 0" = х; Ч Ь имеют противоположные литералы х; и х; (при этом может быть 1~ — — И или ~г = И). Тогда рсзольвентай дизъюнктов Р' и Р" по х, будем называть дизъюнкт Р = т~ Ч 1г (если 1~ — — 1г, то Ф~ Ч $г —— $~). Если Ф~ — — И и $г = И, то положим Р = О.

Лемма 4.21. Для любых формул А и В выполняется равенство

(х; 4 А) (х; ч В) = (х; Ч А)(х, Ч В) (А Ч В).

Доказательство. Если правая часть равна 1, то, очевидно, и левая часть равна 1. Если правая часть равна О, то либо х; Ч А = О, либо х, Ч В = О, либо А Ч В = О. В первых двух случаях левая часть равна О. В последнем случае А = О и В = О. Тогда левая часть равна (х, Ч 0) (х, Ч 0) = х;х; = О. Лемма доказана.

Эта лемма показывает, что добавление к 2-КНФ резольвенты любой пары дизъюнктов не меняет функцию, реализуемую 2-КНФ. Будем просматривать все пары дизъюнктов текущей 2-КНФ и 'строить их резольвенты. Если окажется, что некоторая резольвента отсутствует в текущей 2-КНФ, то добавим ее и начнем просмотр сначала. Так будем делать до тех пор, пока не окажется, что все резольвенты текущей 2-КНФ уже содержатся в ней. Если при этом будет порождена резольвента О, то выдаем ответ: "Исходная 2-КНФ невыполнима", иначе выдаем ответ: "Исходная 2-КНФ выполнима".

Лемма 4.22. Алгоритм обязательно остановится и работавтп полиномиальное„время.

Доказательство. Если длина исходной 2-КНФ равна и, то в ней

Ф ! ~г

не более и переменных, из которых можно построить не более (2и+ 1)

зт

Распознанный текст из изображения:

дизъюнктов с одной или двумя переменными. Поэтому поиск новых резольвент будет повторяться не более (2п+ 1) раз, при этом. число просматриваемых пар дизъюнктов не превосходит (2п + 1)4. Отсюда следует утверждение леммы.

Лемма 4.23. Алгоритм правильно решаетп задачу 2-ВБ1П.

Доказатпельство. 1) Пусть К = Р1Р9 .....О,— исходная 2-КНФ и пусть в конечной КНФ Х' есть сомножитель О. По лемме 4.21 К = К' и, следовательно, К = О, то есть К невыполнима. 2) Пусть в конечной 2-КНФ К' нет О. По построению К' замкнута относительно взятия резольвент, то есть резольвента любых двух дизъюнктов из К' снова содержится в К'. Докажем, что любая 2-КНФ с таким свойством, не содержащая сомножителя О, выполнима. Доказательство проведем индукцией по числу переменных и в 2-КНФ К'.

Базис индукции: и = 1. Тогда К' = х; или К' = х;. В любом случае К' выполнима.

Индуктивный переход. Пусть утверждение верно для 2-КНФ с и ( т переменными и пусть в К' имеется т переменных хг, х9,..., х,„. Тогда

К' = (хш Ч Й1) (хтв Ч ~2) ' .. ' (х|п Ч Фй) (хт Ч Ф1) (хтп Ч ф

(х~ Ч 1,') С1 С9.... С„,

где 1,, ~'- — литералы, либо О, и С1 С9..... ф— 2-КНФ с переменными х1,х9,..., х 1, замкнутая относительно взятия резольвент. По предположению индукции существует набор й = (сг1,..., а 1), на котором С1.С9 ... С„равно 1. Если бы существовали 8, и ~'; такие, что Ц(й) = О и $'-(Й) = О, то было бы и Ц(й) Ч Ф'(й) = О. Но 1; Ч 8' — резольвента дизъюнктов х,„Ч1, и х„, Ч1'. Так как 2-КНФ К' замкнута относительно

т

взятия револьвент, то ~, Ч 1' содержится среди Сг, С9,..., С,. Но это противоречит тому, что С„(й) = 1 при всех и. Следовательно, либо все Х;(й) = 1, либо все Х,'(й) = 1. В первом случае К' выполнима на наборе (Й, 0), во втором — на наборе (Й, 1) .

Теорема 4.15 полностью доказана.

4.8. Некоторые ЖР-полные задачи на графах

*

Теорема 4.16. Задача КЛИКА является МР-полной.

Доказательство. Покажем, что задача ВЫП полиномиально сводится к задаче КЛИКА, Для этого каждому слову а в алфавите языка ВЫП сопоставим пару ~р(а) = (С, й), где С вЂ” некоторый граф и й— натуральное число, так, чтобы в С существовала клика с й вершинами

тогда и только тогда, когда а — выполнимая КНФ. Если а — не КНФ, то положим ~р(а) = (С2, 2), где С9 — граф с 2 вершинами и без ребер (очевидно, в С2 нет клики с 2 вершинами). Пусть теперь а — КНФ и а = Р1 Р2 ....О„где Р, = 1;1Ч1;2Ч...Ч1, — дизъюнкты. Построим граф у(а) = С; = (Ъ; Е) с множеством вершин У и множеством ребер Е следующим образом. Каждому литералу ~; . из а сопоставим вершину и;„ и будем считать,что

(гг;, р„и;,,т,) Е Е ~ (гг ~ гз) и (Ф;, р, ф ~;,Д,).

Положим й = в, где з — число дизъюнктов в а.

Лемма 4.24. В Св есть клика с в вершинами тпогда и только тпоада, коеда КНФ а выполнима.

Доказательство. Пусть КНФ а принимает значение 1 на наборе Й, Тогда Р,(й) = 1 для всех г. Следовательно, для каждого г существует т; такое, что 8;;,. = 1. Тогда среди 11 -„Ф9 „...,8,, нет противоположных литералов. Поэтому любью вершины из гг1 „и9 „..., гг,,, соединяются в С; ребром, то есть образуют клику с з вершинами.

Обратно, пусть в графе С; есть клика с з вершинами г~„,~„и,, ~-„...,и,. г, Тогда г1, г2,..., г, все различны, то есть литералы из семейства М = (1;, -„1;, „...,1;, -,) входят по одному в каждый дизъюнкт КНФ а, причем среди этих литералов нет противоположных. Пусть хг,х2..., х„— все переменные из а. Для каждого й положим х~ = 1, если литерал хг, встречается в М, хь = О, если хг, встречается в М, и хт. — любое, если ни хг,, ни хь нет в М. Тогда на построенном наборе Й все литералы из М обращаются в 1 и, следовательно, все дизъюнкты и вся КНФ а принимают значение 1, то есть КНФ а выполнима. Лемма доказана.

Таким образом переход а — ~ <р(а) является сведением задачи ВЫП к задаче КЛИКА. Распознать, является ли а КНФ, и построить по а граф Са и число й можно за полиномиальное время. Поэтому зто полиномиальное сведение. Так как задача ВЫП ХР-полна и КЛИКА Е 1ЧР, то по теореме 4.13 получаем, что и задача КЛИКА ИР-полна. Теорема 4.16 доказана.

Задача о независимом множестве вершин (НМ).

Вход: пара (С, й), где С вЂ” граф, й — натуральное число.

Вопрос: существуют ли в С й вершин, образующих независимое множество, то есть множество, в котором никакие вершины не соединены ребром в С?

Лемма 4.25. НМ е ИР.

58

59

Распознанный текст из изображения:

Доказательство. Сертификатом является само независимое множество М с Й вершинами (если такое есть). Проверить, что М содер-, жит ровно Й вершин и является независимым, можно за полиномиальное время.

Задача о вершинном покрытии (ВП).

Вход: пара (С, Й), где С вЂ” граф, Й вЂ” натуральное число.

Вопрос: существует ли в С множество М из Й вершин, образующих вершинное покрытие, то есть такое, что любое ребро из С имеет хотя бы один конец в М?

Лемма 4.26. ВП Е ИР.

Доказательство. Сертификатом является само вершинное покрытие М с Й вершинами (если такое есть). Проверить, что М содержит ровно Й вершин и является вершинным покрытием, можно за полиномиальное время.

Теорема 4.17. Задачи НМ и ВП МР-полны.

Доказательство. Сопоставим паре (С, Й) пару (С, Й), где С вЂ” граф, являющийся дополнением к С (то есть в С то же множество вершин У, что и в С, и две вершины соединяются ребром в С тогда и только тогда, когда они не соединяются ребром в С). При этом подмножество М С У является кликой с Й вершинами в С тогда и только тогда, когда М является независимым множеством с Й вершинами в С. Получаем сведение (очевидно, полиномиальное) задачи КЛИКА к задаче НМ. Так как задача КЛИКА МР-полна и НМ Е МР, то задача НМ ХР-полная. Сопоставим паре (С, Й) пару (С,и — Й), где и = Щ число вершин в графе С. При этом подмножество М С У является независимым множеством с Й вершинами в С тогда и только тогда, когда У ~ М является вершинным покрытием с п — Й вершинами в С. Получаем полиномиальное сведение задачи НМ к задаче ВП. Гак как задача НМ ФР-полная и ВП Е ХР, то и задача ВП МР-полная.

Определение. Цикл в графе, проходящий через каждую вершину ровно 1 раз, называется гамильтоновым циклом. Гамильтоновой цепью называется незамкнутая цепь, проходящая через каждую вершину ровно 1 раз.

Задача о гамильтоновом цикле (1'Ц).

Вход:произвольный граф С.

Вопрос: есть ли в С гамильтонов цикл?

Лемма 4.27. ГЦ Е МР.

Доказательство. Для данного графа С с и вершинами сертификатом является последовательность вершин (ю1, з2,..., и„). Алгоритм

~р~~~рки ~~ртификата должен убедиться, что в этом списке столько же вершин, сколько в графе С, что все они различны и что для всех

,..., и — 1 в графе С есть ребро (о., о +1), а также есть ребро ' = 1 2 ... (о„, о1). Все это можно выполнить за полиномиальное время. Теорема 4.18. Задача ГЦ ИР-полна. Доказательство. Построим полиномиальное сведение задачи 3-ВЫП к 3- Ъ|П к задаче ГЦ. Рассмотрим 2 вспомогательных графа: а-граф и,о-граф, изображенные на рис. 1 и 2, соответственно. Рис. 1

Рис. 2

Пусть а-граф (рис. 1) является подграфом некоторого графа С, причем с другими вершинами графа могут соединяться только верши- пыА А В

2 В1 В2> и пУсть в С существует гамильтонов цикл. Нетрудно проверить, что если этот цикл ~~одит внутр ~ графа то он ~б~за~ сразу обоити все внутренние вершины а-графа. При этом, если он входит через вершину А1, то выходит обязательно через В1 и наоборот. Л налогично, если он входит через А2, то выходит через В2 и наоборот. Поэтому условно можно считать, что а-граф имеет всего 2 ребра А1В1 иАВ и я 2 и требуется, чтобы цикл проходил ровно по одному из них.

Пусть,д-граф (рис. 2) является подграфом некоторого графа С, причем с другими вершинами графа С могут соединяться только вершины Р и Я. Если гамильтонов цикл входит в,д-граф через Р или Ь, то он должен сразу обойти все вершины этого Д-графа (и выйти через другую вершину пары Р, Я).

В,д-графе (рис. 2) 3 нижних ребра РЯ, ЯВ и ВЯ будем называть основными, а вершины Р и Я вЂ” граничными.

Лемма 4.28. Не существует гамильтоновой цепи в ~З-графе из вершины Р в вершину Я, проходящей по всем трем основным ребрам РС~,ЯВ,ВЯ. Для любого другого подмножества основных ребер (включая пустое подмножество) существует гамильтонова цепь из н в 1 в Я, проходящая в точности по этому подмножеству основных ребер.

Первая часть этой леммы очевидна, для доказательства второй

Распознанный текст из изображения:

части достаточно рассмотреть все возможные случаи и в каждом построить соответствующую гамильтонову цепь (постройте).

Пусть А — алфавит задачи 3-ВЫП. Каждому слову а Е А* мы' сопоставим граф С так, чтобы в С существовал гамильтонов цикл тогда и только тогда, когда а выполнимая 3-КНФ. Если а е А* и а — не З-КНФ, то сопоставим а граф С с двумя вершинами и 1 ребром. Очевидно, в нем нет гамильтонова цикла. Пусть теперь а = К = В1 ..02 ... Р, — произвольная 3-КНФ с переменными х1,х2,...,х„. Пусть Н1, Н2,...,Н, —,8-графы с граничными вершинами Р-, Я~, 1' = 1, 2,..., в. Соединим ребрами вершины Я и Р.+1 для 1 = 1, 2,..., в — 1. Полученный граф обозначим С1. Через С2 обозначим граф (точнее, мультиграф) с вершинами Со, С1,..., С„, в котором для каждого г = 1,2,...,и есть 2 ребра (С; 1, С,) и нет других ребер. Вершину Р1 графа С1 соединим ребром с Со, а 5, соединим ребром с С„. Из двух ребер (С, 1, С;) одно сопоставим переменной х;, а другое — х,. Первое обозначим е1, второе ео. В каждом подграфе Н ся:новные ребра Р~ф, фВ,-, В;Ь~ сопоставим литералам Ф; 1, 8; з, 8 з дизьюнкта Х)-. Пусть литерал х, встречается в к дизъюнктах П. и в подграфах Н литералу х, соответствуют й ребер е1,е2,...,еь. Между ребром е; = (С, 1, С;), соответствующим х;, и каждым из ребер е1, е~,..., е~ 1

вставим соединительные ребра так, чтобы образовалось й а-графов. Так поступим для всех х,. Аналогично поступим для всех х; с заменой е,' на ео. Полученный граф обозначим Са.

Лемма 4.29. В С; есть гамильтонов цикл тогда и только тогда, когда КНФ К выполнима.

доказательство. Пусть в Св существует гамильтонов цикл И'. По свойствам а-графа (см.выше) можно условно считать, что гамильтонов цикл проходит ровно по одному из ребер А1В1 или А2В2 а-графа. Следовательно, можно считать, что цикл И" сначала проходит по всем вершинам подграфа С1, потом по всем вершинам подграфа С~, при этом выполняется требуемое свойство для каждого а-графа. Для каждой пары ребер ео, е1 в Сз цикл И', очевидно, должен проходить ровно по одному из этих ребер. Для каждого г положим х; = О, если Ж проходит по ео, и х; = 1, если И' проходит по е1. Полученный набор обозначим у = (71,..., у„). Рассмотрим один из подграфов Н, в С1. По лемме 4.28 гамильтонов цикл И~ не проходит по крайней мере по одному из основных ребер подграфа Н.. Пусть этому ребру соспоставлен литерал 1 с переменной х;. Если ~ = х;, то это ребро соединено а-графом с е1, если ~ = х;, то с ео. Так как по данному ребру

цикл И' не проходит, он должен проходить по е1, если 8 = х,, и по е,, если 1 = х;. Из выбора у; получаем, что в любом случае 1( у) = 1 и, о

следовательно, .О. (ф) = 1. Поскольку это верно для всех 7', то К( у) = 1, то есть КНФ Х выполнима.

Обратно, пусть КНФ К выполнима и К(у) = 1, где у (у~,..., ~„). Проведем цикл И' по подграфу С~ так, чтобы для каждого г = 1, 2,..., и он проходил по е,, если у, = О, и по е1, если у, = 1. Тогда

о

по свойствам а-графов цикл И' не может проходить по основному ребру подграфа С1, которому приписан литерал ~, такой, что 1( у) = 1, и обязан проходить по основному ребру, если ему приписан литерал 1, такой, что 1® = О. Так как В (у) = 1 для всех 1, то в каждом подграфе Н. существует хотя бы одно ребро, такое, что для соответствующего ему литерала 1 выполняется 1Я) = 1. Следовательно в каждом подграфе Н существует одно, два или три основных ребра, таких, что цикл И' не должен по ним проходить, и должен проходить по остальным основным ребрам. По лемме 4.28 в каждом Н. можно построить гамильтонову цепь, удовлетворяющую этим требованиям, и в целом в графе С; можно построить гамильтонов цикл. Лемма доказана.

Проверить, является ли слово а Е А* З-КНФ, и построить граф Сд, если а = К вЂ” это З-КНФ, можно за полиномиальное (от длины а) время. Поэтому мы получаем полиномиальное сведение задачи 3-ВЫП к задаче ГЦ. Так как задача 3-ВЫП ХР-полна и ГЦ Е 1ЧР, то и задача ГЦ ХР-полна. Теорема 4.18 доказана.

Интересно, что следующая близкая задача оказывается полиномиальной.

Определение. Мультиграфом называется граф, в котором разрешены кратные ребра (то есть ребра, соединяющие одну и ту же пару вершин).

Определение. Эйлеровым циклом в мультиграфе называется цикл, проходящий по каждому ребру ровно один раз и проходящий по всем вершинам.

Теорема 4.19. Эйлеров цикл в мультиграфе сушествует тогда и только тогда, когда мультиграф связный и степени всех вершин в мультиграфе четны, причем существует полиномиальный алгоритм, который, в случае, когда мультиграф связный и степени всех вершин и мультиграфе четны, строит эйлеров цикл.

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

б2

63

Распознанный текст из изображения:

5. Задачи оптимизации

должна равняться 2Й. Пусть теперь все степени четны. Выберем любую вершину и1 и будем строить путь по ребрам, используя любые еще не пройденные ребра, до тех пор, пока не окажемся в тупике, Так . как степень любой вершины четна, то тупик не может образоваться ни в одной вершине, отличной от ~1. В результате получим некоторый цикл. Если этот цикл не содержит всех ребер мультиграфа, то, в силу связности мультиграфа, существует на построенном цикле хотя бы одна вершина и2, которая инцидентна не пройденному ребру. Тогда рассмотрим уже построенный цикл, как начинающийся и кончающийся в вершине и~. После чего опять продолжим построение цикла из вершины и2. Этот процесс будем продолжать рекурсивно, пока в цикл не войдут все ребра. Описанный алгоритм, очевидно, полиномиален относительно числа ребер.

В практических приложениях часто возникают задачи оптимизации, которые имеют следующую структуру. Каждому входу х сопоставляется некоторое множество У~ допустимых решений. Задан функционал Р: У, — ~ .й, где й,— множество действительных чисел. Требуется найти

тш Р(у) или шах Р(у)

уе~ х реУ~

или то допустимое решение уо, на котором достигается оптимальное значение функционала. Если функционал Е вычисляется быстро, то найдя оптимальное допустимое решение, мы можем легко получить и оптимальное значение функционала Р „,. Обратное, вообще говоря, не нснсс может существовать быстрый алгоритм, который находит Ро,, не находя оптимального решения.

С каждой задачей оптимизации можно связать задачу распознавания. При этом на вход кроме ю подается число й и спрашивается, верно ли, что Р,, < Й (или Р, > Й).

На практике для решения задач оптимизации часто используются алгоритмы, называемые жадными или градиентными. В таких алгоритмах допустимое решение строится постепенно по шагам, причем на каждом шаге делается выбор, оптимальный для данного шага. Как мы увидим ниже, такой подход не всегда приводит к оптимальному решению в целом. Однако для следующей задачи он всегда да«т оптимальное решение. Напомним, что деревом называется любой неориентированный связный граф без циклов. Подграф С1 графа С называется остовным, если С1 содержит все вершины графа С. Через К„обозначается полный граф на н вершинах, то есть граф, в котором каждая пара вершин соединена ребром.

5.1. Задача о кратчайшем остовном дереве

Вход: неориентированный полный граф К„, в котором для любого ребра е задан вес ш(е) > О.

Требуе~ися: выделить в К„остовное дерево с минимальной суммой весов ребер.

Замечание. На практике это означает требование построить сеть минимальной стоимости, связывающую п данных объектов.

Напомним некоторые факты из теории графов (3].

Утверждение 1. Если в графе с п вершинами число ребер д ( п — 1, то граф не связный.