Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 245
Текст из файла (страница 245)
Во-вторых, для многих приемлемых вычислительных моделей задач~ которая решается в течение полиномиалъного времени в одной модели, может быть решена в течение полиномиального времени и в другой. Например, в большей части книги рассматривается класс задач, разрешимых в течение полиномиального времени с помощью последовательных машин с произвольным доступом к памяти. Зтот класс совпадает с классом задач, разрешимых в течение полииомиального времени на абстрактных машинах Тьюринга'. Он также совпадает с классом задач, разрешимых в течение полиномиапьного времени на параллельных компьютерах, если зависимость количества процессоров от объема входных данных описывается полиномиальной функцией.
В-третьих, класс задач, разрешимых в течение полиномиального времени, обладает полезными свойствами замкнутости, поскольку множество полиномов замкнуто относительно операций сложения, умножения и композиции. Например, если выход одного алгоритма с полиномиальным временем работы соединить со входом другой такой задачи, получится полиномиальиый составной алгоритм. В упр. 34.1.5 требуется показать, что если алгоритм с полиномиальным временем работы фиксированное количество раз вызывает подпрограммы с полиномиальным временем работы и выполняет дополнительные действия также за полиномиальное время, то и общее время работы такого составного алгоритма является полиномиальным. Абстрактные задачи Чтобы получить представление о классе задач, разрешимых за полнномнальное время, сначала необходимо формально описать само понятие "задача".
Подробное рассмотрение модели Тьюринга можно найти е книгак Хопкрск]гта (Норсгой) и Ульмана (П)ьгпю) [179], а также Льюиса (конча) и Пападимитриу (Рарм)пшгпон) 12)5]. Рлаеа 3К ФР-лолиоюа 1! 03 Определим абсязрактиуау задачу (аЬ|ггасг ргоЫезп) Я как бинарное отношение между множеством эаэемпляроа ((пзрапсез) задач 1 и множеством реклелий (бо!Шюпз) задач 5. Например, экземпляр задачи о поиске кратчайшего пути ЯНОВТЕЯТ-РАТН состоит из трех элементов: графа и двух вершин. Решением этой задачи является последовательность вершин графа; при этом пустая последовательность может означать, что искомого пути не существует.
Сама задача ЯНОНТЕЯТ-РАТН представляет собой отношение, сопоставляющее каждому экземпляру графа н двум его вершинам кратчайший путь по графу, соединяющий зти две вершины. Поскольку кратчайший путь может быть не единственным, конкретный экземпляр задачи может иметь несколько решений. Представленная выше формулировка абстрактной задачи носит более широкий характер, чем требуется для наших целей. Как мы уже видели, теория ХР-полноты ограничивается рассмотрением задач принятия рекаеиия (бес!з!Оп ргоЫешз), решения которых имеют вид "да/нет".
В этом случае абстрактную задачу принятия решения можно рассматривать как функцию, отображающую экземпляр множества 1 на множество решений (О, Ц. Например, задача принятия решения, соответствующая задаче ЯНОНТЕЯТ-РАТН, — рассмотренная выше задача поиска пути РАТН. Если з = (С, и, зз, lс) — экземпляр задачи принятия решения РАТН, то равенство РАТН(з) = 1 (да) выполняется, если количество ребер в кратчайшем пути из вершины и в вершину зз не превышает )с; в противном случае РАТН(з) = 0 (нет).
Многие абстрактные задачи являются не задачами принятия решения, а задачами олязимизазбии (орйп!яацоп ргоЫеглз), в которых некоторое значение подлежит минимизации или максимизации. Однако ранее мы убедились, что обычно не составляет труда сформулировать задачу оптимизации как задачу принятия решения, которая не сложнее исходной. Кодирование Если абстрактная задача решается с помощью компьютерной программы, экземпляры задач необходимо представить в виде, понятном этой программе.
Кодирование (епсогйпй) множества Я абстрактных объектов — зто отображение е множества Я на множество бинарных строкз. Например, всем известно, что натуральные числа з"( = (0,1,2,3,4,...) кодируются строками (0,1,10,11,100,...). В этой кодировке е(17) = 10001. Каждый, кто интересовался, как в компьютере представляются символы клавиатуры, вероятно, знаком с кодами АБС11. В кодировке АБСП представление символа А выглядит как 1000001. В виде бинарной строки можно закодировать даже составной объект. Для этого конструируется комбинация, состоящая из представлений элементов, которые содержит в себе этот объект. Многоугольники, графы, функции, ориентированные пары, программы — все это можно закодировать бинарными строками.
Таким образом, компьютерный алгоритм, который "решает" некоторую абстрактную задачу принятия решения, фактически принимает в качестве вход- зобласть значений очображенил е — зто необкзательно Бинарные строк»; лслойлет любое множество строк, состоящих из символов конечиото алфавита, содержащего не менее двух символов.
Часть РТП Избрпнные темы Л04 ных данных закодированный экземпляр задачи. Назовем задачу, множество экземпляров которой является множеством бинарных строк, конкретной (сопсге(е ргоЫеш). Говорят, что алгоритм реигает (зо1чез) конкретную задачу в течение времени 0(Т(п)), если для заданного эюемпляра задачи г длиной и = ((~ с его помощью можно получить решение за время О(Т(п))з.
Поэтому конкретная задача разрегнима в течение нолиномнального времени (ро!упоппа1-(ппе зо!чаЫе), если существует алгоритм, позволяющий решить ее за время 0(п") для некоторой константы lс. Теперь можно формально определить класс сложности Р (сошр!ехйу с1ат Р) как множество конкретных задач принятия решения, разрешимых за полиномиальное время. С помощью кодирования абстрактные задачи можно отображать на конкретные. Данную абстрактную задачу принятия решения (,1, отображающую множество экземпляров 1 на множество (О, Ц, с помощью кодирования е: Т вЂ” у (О, 1)' можно свести к связанной с ней конкретной задаче принятия решения, которая будет обозначаться как е(Я)4.
Если О(() е (0,1) — решение экземпляра абстрактной задачи х е Т, то оно же является и решением экземпляра конкретной задачи е(е) Е (О, 1)'. Заметим, что некоторые бинарные строки могут не представвпь осмысленного эюемпляра абстрактной задачи. Для удобства мы будем предполагать, что любая такая строка произвольным образом отображается на О. Таким образом, конкретная задача имеет те же решения, что и абстрактная, если ее экземпляры в виде бинарных строк представляют закодированные экземпляры абстрактной задачи. Было бы неплохо расширить определение разрешимости в течение полиномнального времени для конкретных задач на абстрактные задачи, воспользовавшись в качестве связующего звена кодами; однако хотелось бы, чтобы определение не зависело от вида кодировки. Другими словами, эффективность решения задачи не должна зависеть от того, как она кодируется.
К сожалению, на самом деле существует достаточно сильная зависимость от кодирования. Например, предположим, что в качестве входных данных алгоритма выступает только целое число Е и что время работы этого алгоритма равно су()с). Если число Е передается как укорное (цпагу), т.е.
в виде строки, состоящей из )с единиц, то время работы алгоритма для входных данных длины п равно О(п) (выражается полиномиальной функцией). Если же используется более естественное бинарное представление числа к, то длина входной строки равна и = (1б /с) + 1. В этом случае время работы алгоритма равно су(к) = су(2"), т.е. зависит от объема входных данных как показательная функция.
Таким образом, в зависимости от способа кодирования алгоритм может как выполняться за полиномиальное время, так и иметь время работы, превосходящее полиномиальное. зцредполагается, что выходные данные алгорнтма отделены от его входных данных.
Поскольку лля лолучення каждого аыходного бита требуется по крайней маре адин злементарный временной интервал, а асспг имеется О(Т(п)) временных ннтераалоа, обьем выходных данных представляет собой О(Т(п)). Мы обозначаем через (О, 1)* множестео асах строк, состааленных нз снмаолоа множества (О, 1). П05 Глава 34. )(гР-пояногла Поэтому юдирование абстрактной задачи — достаточно важный вопрос для нашего понимания полиномиального времени. Невозможно вести речь о решении абстрактной задачи, не представив подробного описания кодировки. Тем не менее, если отбросить такие "дорогостоящие" коды, как унарные, само кодирование задачи на практике будет мало влиять на то, разрешима лн задача в течение полиномиального времени.
Например, если представить целые числа в троичной системе счисления, а не в двоичной, это не повлияет на то, разрешима ли задача в течение полиномиального времени, поскольку целое число в троичной системе счисления можно преобразовать в целое число в двоичной системе счисления за полиномиаяьное время. Говорят, что функция 1; (О, Ц' -+ (0,1)" вычислима за лолилаииальное время (ро)упоппа(-(ппе сошрпгао)е), если существует алгоритм А с полиномиальным временем работы, который для произвольных входных данных х е (О, Ц' возвращает выходные данные 1(т). Для некоторого множества 1 экземпляров задач две кодировки, е1 и ез, называются лолиномиально связанными (ро!упоппа!!у ге(а(е(!), если существуют такие две вычислимые в течение полиномиального времени функции, 1(з и 1з), что для любого экземпляра в е 1 выполняются равенства 1уз(е)(в)) = еэ(!) и )ж(еэ(з)) = е)(з) . Другими словами, закодированную величину еэ(!) можно вычислить на основе закодированной величины е((в) с помощью алгоритма с полиномиальным временем работы и наоборот.
Если две кодировки, е) и еэ, абстрактной задачи полиномиально связаны, то, как следует из представленной ниже леммы, разрешимость задачи в течение полиномиального времени не зависит от используемой кодировки. Лемма 34.1 Пусть Я вЂ” абстрактная задача принятия решения, определенная на множестве экземпляров 1, а е) и еэ — полиномиально связанные кодировки множества 1. В этом случае е) ((,)) Е Р тогда и толью тогда, когда ез((4) й Р. Лекаэаувельслвво. Достаточно доказать толью прямое утверждение, поскольку обратное утверждение симметрично по отношению к прямому.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
