Алгоритмы - построение и анализ (1021735), страница 226
Текст из файла (страница 226)
Например, всем известно, что натуральные числа 1ь( = (1, 2,...) кодируются строками (1, 10, 11,...). В этой кодировке е (17) = 10001. Каждый, кто интересовался, как в компьютере представляются символы клавиатуры, знаком с кодами АБСП или кодами ЕВС131С. В кодировке АБСП представление символа А выглядит как 1000001. В виде бинарной строки можно закодировать даже составной объект. Для этого юнструируется комбинация, состоящая из представлений элементов, которые содержит в себе этот объект. Многоугольники, графы, функции, ориентированные пары, программы — все это можно заюдировать бинарными строками.
Таким образом, компьютерный алгоритм, который "решает"' некоторую абстрактную задачу принятия решения, фактически принимает в качестве входных данных закодированный экземпляр задачи. Назовем задачу, множество зОбласть значений отображения е — не обязательно бяяаряме строки; подойдет любое множество строк, состоящих из символов конечного алфавита, содержащего не менее двух символов. 1094 Часть Ч!1. Избранные темы экземпляров которой является множеством бинарных строк, кон«ретной (сопсге(е ргоЫеш).
Говорят, что алгоритм решает (зо1чез) конкретную задачу в течение времени О (Т (гз)), если для заданного экземпляра задачи з длиной п = ~з~ с его помощью можно получить решение в течение времени О (Т (п))~. Поэтому конкретная задача разрешима в течение нолинаниального времени (ро1упоппа1мппе зо1уаЫе), если существует алгоритм, позволяющий решить ее за время О (гз~), где lс — некоторая ыэнстаита. Теперь класс сложности Р (сошр!ех(гу с1азз Р) можно формально определить как множество конкретных задач принятия решения, разрешимых в течение полиномиального времени.
С помощью кодирования абстрактные задачи можно отображать на конкретные. Данную абстрактную задачу принятия решения Я, отображающую множество экземпляров на множество (О, Ц, с помощью кодирования е: Х -+ (О, Ц можно свести к связанной с ней конкретной задаче принятия решения, которая будет обозначаться как е (Я)4. Если Я (з) Е (О, Ц вЂ” решение экземпляра абстрактной задачи з б 1, то оно же является и решением экземпляра конкретной задачи е(з) Е (О, Ц'. Заметим, что некоторые бинарные строки могут не представлять осмысленного экземпляра абстрактной задачи.
Для удобства мы будем предполагать, что любая такая строка произвольным образом отображается на О. Таким образом, конкретная задача имеет те же решения, что и абстрактная, если ее экземпляры в виде бинарных строк представляют закодированные экземпляры абстрактной задачи. Попытаемся расширить определение разрешимости в течение полиномиального времени для конкретных задач на абстрактные задачи, воспользовавшись в качестве связующего звена кодами; однако хотелось бы, чтобы определение не зависело от вида кодировки.
Другими словами, эффективность решения задачи не должна зависеть от того, как она кодируется. К сожалению, на самом деле существует достаточно сильная зависимость от кодирования. Например, предположим, что в качестве входных данных алгоритма выступает только целое число Й и что время работы этого алгоритма равно 9 (lс). Если число lс передается как унарное (влагу), т.е.
в виде строки, состоящей из )с единиц, то время работы алгоритма для входных данных длины п равно О (гг) (выражается полиномиальной функцией). Если же используется более естественное бинарное представление числа «, то длина входной строки равна и = ~1бк) + 1. В этом случае время работы алгоритма равно О ()с) = О (2п), т.е.
зависит от обьема входных данных как Предполагается, что выходные данные алгоритма отделены от его входных данных. Поскольку для получения каждого выходного бита требуется по крайней мере один элементарный временной интервал, а всего имеется 0 (Т (и)) временных интервалов, объем выходных данных должен быть 0(Т(п)) . Как вскоре станет понятно, (О, 1)' обозначает множество всех строк, состоящих из символов множества (О, Ц. Глава 34. г)Р-полнота 1095 показательная функция. Таким образом, в зависимости от способа кодирования, алгоритм работает в течение полиномиального времени или превосходит его. Поэтому кодирование абстрактной задачи — достаточно важный вопрос для нашего понимания полиномиального времени.
Невозможно вести речь о решении абстрактной задачи, не представив подробного описания кодировки. Тем не менее, если отбросить такие "дорогостоящие" коды, как унарные, само кодирование задачи на практике будет мало влиять на то, разрешима ли задача в течение полиномиального времени. Например, если представить целые числа в троичной системе счисления, а не в двоичной, это не повлияет на то, разрешима ли задача в течение полиномиального времени, поскольку целое число в троичной системе счисления можно преобразовать в целое число в двоичной системе счисления в течение полиномиального времени.
Говорят, что функция У: (О, Ц' — 10,1)' вычаслима в течение полиномиалъного времени (ро1упош)а1-1нпе сотри1аЫе), если существует алгоритм А с полиномиальным временем работы, который для произвольных входных данных х Е 10, 1)* возвращает выходные данные )' (х). Для некоторого множества 1, состоящего из экземпляров задач, две кодировки е1 и ез называются полинамиалъно свяэанпыыи (ро1упопна11у ге1а1ед), если существуют такие две вычислимые в течение полиномиального времени функции ~гз и гз1, что для любого экземпляра ы1 выполняются равенства )ш (ег (з)) = ез (з) и )з1 (ез (з)) = е1 (з)~. Другими словами, закодированную величину ез (з) можно вычислить на основе закодированной величины е1 (з) с помощью алгоритма с полиномиальным временем работы и наоборот.
Если две кодировки ет и ез абстрактной задачи полиномиально связаны, то, как следует из представленной ниже леммы, разрешимость задачи в течение полиномиального времени не зависит от используемой кодировки. Лемма 34.1. Пусть Я вЂ” абстрактная задача принятия решения, определенная на множестве экземпляров 1, а е1 н ез — полиномиально связанные кодировки множества 1, В этом случае е1 (Я) е Р тогда и только тогда, когда ез Я) е Р.
Дпкязапзелъспыо. Достаточно доказать только прямое утверждение, поскольку обратное утверждение симметрично по отношению к прямому. Поэтому предположим, что задачу е1 Я) можно решить за время О (и"), где й — некоторая константа. Далее, предположим, что для любого экземпляра з задачи кодирование Е1 (З) МОЖНО ПОЛУЧИТЬ ИЗ КОДИРОВаНИЯ ЕЗ (З) За ВРЕМЯ О (Гзс), ГДЕ С вЂ” НЕКОтО- рая константа, а и = ~ез (з)~. Чтобы решить задачу ез (Я) с входными данными зкроме того, накладывается техническое требование, чтобы функции )ззи,5г "отображали неэкземпляры в неэкземпляры". Неэкземпляр (поп(пзгапсе) в кодировке е — это такая строка к б б (О, 1)', что не существует экземпляра з, лля которого е(1) = к.
Потребуем, чтобы равенство Ггз (л) = у выполнялось для каждого неэкэемпляра к в юдировке ен где у — некоторый неэкземпляр в юднровке ез, а равенство,Гзг (и') = у' — для каждого незкземпляра к' в кодировке ез, где у' — неюторый неэкземпляр в кодировке ег. Часть ЧП. Избранные темы 1096 ез(1), сначала вычисляется ез (1), после чего алгоритм запускается для решения задачи е1 (Я) с входными данными е1 (1). Сколько времени это займет? Для преобразования кодировки требуется время 0 (и'), поэтому выполняется равенство ~е1 (1) ~ = О (п'), поскольку обьем выходных данных алгоритма на последовательном компьютере не может превосходить по величине время его работы. Решение задачи с входными данными е1 (1) занимает время О (~е1 (1) ~ ~ = 0 (и'"), котоь'1 рое является полиномиальным, поскольку и с, и /с — константы. 6 Таким образом, тот факт, в каком виде закодированы экземпляры абстрактной задачи — в двоичной системе счисления или троичной, — не влияет на ее "сложность", т.е.
на то, разрешима она в течение полиномиального времени или нет. Однако если эти экземпляры имеют унарную кодировку, сложность задачи может измениться. Чтобы иметь возможность осуществлять преобразование независимым от кодировки образом, в общем случае предполагается, что экземпляры задачи закодированы в произвольном рациональном и сжатом виде, если специально не оговаривается противное. Точнее говоря, предполагается, что кодирование целых чисел полиномиально связано с их бинарным представлением и что кодирование ограниченного множества полиномиально связано с его кодированием в виде списка элементов, взятых в скобки и разделенных запятыми.
(Одна из таких схем кодирования — АБСП.) Располагая таким "стандартным" кодом, можно получить рациональный код других математических объектов, таких как кортежи, графы и формулы. Для обозначения стандартного кода объекта этот объект будет заключаться в угловые скобки. Таким образом, (С) обозначает стандартный код графа С. До тех пор пока неявно используется код, полиномиально связанный с таким стандартным кодом, можно прямо говорить об абстрактных задачах, не ссылаясь при этом на какой-то отдельный код, зная, что выбор кода не повлияет на разрешимость абстрактной задачи в течение полиномиального времени.
С этого момента в общем случае предполагается, что все экземпляры задачи представляют собой бинарные строки, закодированные с помощью стандартного кодирования, если явно не оговаривается противное. Кроме того, в большинстве случаев мы будем пренебрегать различием между абстрактными и конкретными задачами. Однако на практике читателю следует остерегаться тех возникающих на практике задач, в которых стандартное кодирование не очевидно и выбор кодирования имеет значение. Структура формальных языков Один из аргументов, свидетельствующих в пользу удобства задач принятия решения, заключается в том, что для них можно использовать алгоритмы, позаимствованные из теории формальных языков. Здесь стоит привести некоторые Глава 34.
ИР-полнота 1097 определения из этой теории. Алфавиию Е (а!рЬабе1 Е) — это конечное множество символов. Язык Ь (!апянаяе Ь), определенный над множеством Е, — это произвольное множество строк, состоящих из символов из множества Е. Например, если Е = (О, Ц, то множество Ь = (10,11,101,111,1011,...) является языком бинарного представления простых чисел. Обозначим пустую строку (ешргу зизак) через е, а лусюой язык (ешр1у 1апяиаяе) — через 11.
Язык всех строк, заданных над множеством Е, обозначается через Е*. Например, если Е = (О, Ц, то Е' = (е, О, 1, 00, 01, 10, 11,... ) — множество всех бинарных строк. Любой язык Ь над множеством Е является подмножеством множества Е'. Над языками можно определить ряд операций. Наличие таких операций из теории множеств, как обьединение (ишоп) и пересечение (т1егзес1юп), непосредственно следует из теоретико-множественной природы определения языков. Дополнение (согпр1ешел1) языка Ь определим с помощью соотношения Х = Е' — Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
