назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [ 131 ] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


131

NP-ПОЛНЫХ задач заключается в доказательстве более слабых результатов вида: «если Р f NP, то II е NP/P».

Основная идея такого условного подхода основана на идее полиномиальной сводимости. Будем говорить, что имеет место полиномиальная сводимость языка L\ с к языку 11 е если существует функция /: 271 * -> 22*, удовлетворяющая двум условиям:

1)существует ДМТ-программа, вычисляющая f с временной сложностью, ограниченной полиномом;

2)для любого g Z1 *, g II в том и только в том случае, еслиДХ) е 12. Если II полиномиально сводится к 12, то будем писать II оо 12 и говорить «L\ сводится к L2» (опуская слово полиномиально).

Если L1 полиномиально сводится к 12, то будем писать II оо 12. Важность понятия полиномиальная сводимость вытекает из следующей леммы.

Лемма 12.1. Если II оо 12, то из 12 е Р следует, что II е Р (эквивалентно: из II Р следует, что 12 Р).

Доказательство. Пусть 2Л и 22 алфавиты языков II и 12 соответственно, функция /: 271* -> 22* осуществляет полиномиальную сводимость II к 12, Mf- полиномиальная ДМТ-программа, вычисляющая/ и Ml - полиномиальная ДМТ-программа, распознающая 12. Полиномиальная ДМТ-программа, распознающая II, может быть получена композицией программы Mf и Ml. Ко входу X е 271* вначале применяется Mf чтобы построить f(X) g 272*. Затем к fiX) применяется программа М2, выясняющая верно ли, чтоДХ) g 12. Поскольку X € II тогда и только тогда, когда fX) е 12, то это описание дает ДМТ-программу, распознающую II. То, что время работы этой программы ограничено полиномом, немедленно следует из полиномиальности программ Mf и Ml. Точнее, если Р/ и Р2 - полиномы, ограничивающие время работы программ Mf и М2 соответственно, то f{X) < Pf\X\)\, а время работы только что построенной программы, как нетрудно видеть, ограничено функцией 0(P/(Z) + P2(Pf{\X\)), которая является полиномом от \Х\. Лемма доказана.

Если III и 112 - задачи распознавания, а el и е2 - их схемы кодирования, то будем писать III оо 112 (относительно заданных схем кодирования), если существует полиномиальная сводимость языка 1(111, el) к 1(112, е2). Когда будет действовать стандартное предположение о «разумности» используемых схем кодирования, упоминание о конкретных схемах кодирования как обычно будет опускаться. Таким образом, на уровне задач полиномиальная сйодимость задачи распознавания П\ к за-400



даче распознавания П2 означает наличие функции f. Dm - Dn2-, удовлетворяющей двум условиям:

1)/вычисляется полиномиальным алгоритмом;

2)для всех / g / g Ym тогда и только тогда, когда ДУ) g ¥п2. Отношение полиномиальной сводимости особенно удобно, поскольку

оно является транзитивным. Это устанавливает следующая лемма. Лемма 12.2. Если Z1 оо Z2 и Z2 оо Z3, то L\ оо Z3.

Доказательство. Пусть 271, 272, 273 - алфавиты языков Ы, L2, L3 соответственно. Функция /1: 271* -> 272* реализует полиномиальную сводимость L2 к 13. Тогда функция/: 271* -> 273*, которая для всехХ g 271* определяется соотношением ДА) = f2(f\{X)) реализует исходную сводимость языка Ы к языку L3. Действительно, ДА) g L3 тогда и только тогда, когда Х g II, а вычислимость/за полиномиальное время получается с помощью рассуждений, аналогичными рассуждениям, использованным при доказательстве леммы 12.1.

Доказав лемму 12.2, можно говорить, что языки II и 12 (соответственно задачи распознавания Ш и П2) полиномиально эквивалентны, если они сводятся друг к другу, т.е. II оо 12 и 12 оо Ц (имеет место сводимость III 00 112 и 112 00 III). Лемма 12.2 утверждает, что это отношение является отношением эквивалентности, а также, что отношение «оо» определяет частичное упорядочение возникающих классов эквивалентности языков (задач распознавания). На самом деле класс Р- это наименьший относительно этого частичного порядка класс эквивалентности и с вычислительной точки зрения его можно рассматривать как класс самых легких языков задач распознавания. Класс NP-полных языков задач распознавания дает нам другой класс эквивалентности, который характеризуется тем, что он содержит «самые трудные» языки задач распознавания из NP.

Язык L называется NP-полным, если I g NP и любой другой язык I g NP сводится к I. Говоря неформально, задача распознавания П называется NP-полной, если П е NP и любая другая задача распознавания Я g NP сводится к Я. Таким образом, лемма 12.1 позволяет отождествлять NP-полные задачи с «самыми трудными задачами из NP». Если хотя бы одна NP-полная задача может быть решена за полиномиальное время, то и все задачи из NP также могут быть решены за полиномиальное время. Если хотя бы одна задача из NP труднорешаема, то и все NP-полные задачи труднорешаемы.

Следовательно, любая NP-полная задача II обладает свойством, которое сформулировано в начале настоящего раздела: если Р Ф NP, то И е



NP/P. Точнее II e P тогда и только тогда, когда Р = NP. В предложении, что Р Ф NP, можно дать гипотетическую картину класса NP (рис. 12.6).

Рис. 12.6

Из рис. 12.6 видно, что если предположить, что класс Р отличен от NP, то должны существовать задачи из NP, не разрешимые за полиномиальное время и не являющиеся NP-полными.

В дальнейшем мы будем изучать в основном NP-полные задачи. В начале настоящего раздела говорилось о том, что имеются простые методы доказательства NP-полноты задачи, то для этого необходимо доказать, что любая задача из NP сводится к некоторому кандидату на NP-полную задачу. Следующая лемма указывает простой путь доказательства NP-полноты новой задачи П, если известна хотя бы одна NP-полная задача.

Лемма 12.3. Если Z1 и Z2 принадлежит классу NP, Ь\ - это NP-полный язык и II 0012, то L2 также NP-полный язык.

Доказательство. Так как L2 е NP, то достаточно показать, что для всякого и € NP и сводится к 12. Рассмотрим любой язык U g NP. Так как Ы - это NP-полный язык, то U сводится к II. В силу транзитивности отношения 00 из сводимости II оо 12 следует I оо L2. Лемма доказана.

Из доказанной леммы следует, что для доказательства NP-полноты новой задачи II показать:

1)IIgNP;

2)Какая-то одна известная NP-полная задача сводится к П.

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

В настоящее время известен обширный список NP-полных задач (среди которых рассмотренная нами: коммивояжер).

При анализе любой новой задачи, связанной, например, с оптимальным распределением ресурсов в экономической системе, естественно сначала задать вопрос: «Можно ли рассматриваемую задачу решить по-402

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [ 131 ] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]