Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 226
Текст из файла (страница 226)
Например, предположим, что в качестве входных данных алгоритма выступает только целое число Й и что время работы этого алгоритма равно 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) языка Ь определим с помощью соотношения Х = Е' — Ь. Конкатенацией (сопсагепайоп) двух языков Ь| и Ьз является язык Ь = (хзхз '. хз с Ь| и хз Е Ьз) .
Замыканием (с1озпге), или замыканием Клинц (К!еепе згаг), языка Ь называется язык Ь* = (е) ОЬОЬ~ОЬ О где Ьь — язык, полученный в результате lс-кратной конкатенации языка Ь с самим собой. С точки зрения теории языков множество экземпляров любой задачи принятия решения 1,> — это просто множество Е', где Е = (О, Ц. Поскольку множество () полностью характеризуется теми экземплярами задачи, в которых выдается ответ 1 (да), это множество можно рассматривать как язык Ь над множеством Е = = (О, Ц, где Е = (х Е Е': Я (х) = Ц.
Например, задаче принятия решения Рлтн соответствует язык Рлтн = ((С, и, с, к): С = (К Е) — неориентированный граф, и,оба к > 0 — целое число, и в С существует путь от и до с, состоящий не более чем из )с ребер). (Для удобства иногда одно и то же имя (в данном случае это имя РАтн) будет употребляться и для задачи принятия решения, и для соответствующего ей языка.) Схема формальных языков позволяет в сжатом виде выразить взаимоотношение между задачами принятия решения и алгоритмами их решения. Говорят, что 1098 Часть Ч!!. Избранные темы алторитм А принимает (ассер!з) строку х е (О, Ц*, если для заданных входных данных х выход алгоритма А (х) равен 1.
Язык, принимаемый (ассер!ед) алгоритмом А — это множество строк Ь = (х е (О, Ц': А (х) = Ц, т.е. множество строк, воспринимаемых алгоритмом. Алгоритм А отвергает (ге!ее!з) строку х, если А(х) = О. Если язык Ь принимается алгоритмом А, этот алгоритм не обязательно отвергает строку х ф г,, предоставляемую в качестве его входных данных. Например, алгоритм может быть организован в виде бесконечного цикла. Язык й распознаетсп (оесЫед) алгоритмом А, если каждая бинарная строка этого языка принимается алгоритмом А, а каждая бинарная строка, которая не принадлежит языку Ь, отвергается этим алгоритмом. Язык Е принимаетсл за пвлиномиольное время (ассар!еб ш ро1упоппа1 йпе) алгоритмом А, если он принимается алгоритмом А и, кроме того, если существует такая константа lс, что для любой и-символьной строки х Е Ь алгоритм А принимает строку х за время О (пь).
Язык й распознаетсл за поли«ам«аль«ее время (оесЫеб ш ро!упоппа1 пше) алгоритмом А, если существует такая константа «, что для любой и-символьной строки х е (О, Ц' алгоритм за время 0 (и") правильно выясняет, принадлежит ли строка х языку Ь. Таким образом, чтобы принять язык, алгоритму нужно заботиться только о строках языка Ь, а чтобы распознать язык, он должен корректно принять или отвергнуть каждую строку из множества (О, Ц'. Например, язык Рлтн может быть принят в течение полиномиального времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
