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


[Старт] [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]


130

ние НДМТ-программы осуществляется в точности по тем же правилам, что и ДМТ-программа. Угадывающий модуль и его головка в вычислении больше не участвуют, выполнив свою роль, т.е. записав на ленте слово-догадку. Слово-догадка может (и обычно будет) просматриваться читающей / пишущей головкой в процессе проверки. Выполнение заканчивается тогда, когда управляющее устройство перейдет в одно из двух заключительных состояний (ду или дмУ, оно называется принимающим вычислением, если остановка происходит в состоянии ду. Все остальные вычисления, заканчивающиеся или нет, называются непри-нимающими.

Отметим, что любая НДМТ-программа М может иметь бесконечное число возможных вычислений при данном входе X, по одному для каждого слова-догадки из Г*,

Будем говорить, что НДМТ-программа М принимает X, если по крайней мере одно из ее вычислений на входе Xявляется принимающим.

Язьпс, распознаваемый программой М, - это язык Lm = {X е М принимает X}.

Время, требующееся недетерминированной программе М для того, чтобы принять слово X €. Lm, - это минимальное число шагов, выполняемых на стадии угадывания и проверки до момента достижения заключительного состояния ду, где минимум берется по всем принимающим вычислениям программы М на входе X Временная сложность НДМТ-программы М- это функция Тм. 2 2, определяемая следующим образом:

TiJji) = max ({1} U {т: существует X е Lm, 1 = « такое, что время принятия X программой М равно т}).

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

НДМТ-программа назьшается НДМТ-программой с полиномиальным временем работы, если найдется полином Р такой, что Тм(г1) < Р(п) ддя всех « > 1. Наконец класс NP формально определяется так:

NP = {I: существует НДМТ-программа М с полиномиальным временем работы такая, что Lm-L)

Нетрудно установить взаимосвязь между этими формальными определениями и предшествующими неформальными.

Будем говорить, что задача распознавания принадлежит классу NP при схеме кодирования е, если L (II, е) е NP. Как и в случае класса Р



мы говорим, что II лежит в NP, не упоминая конкретную схему кодирования, когда ясно, что некоторая разумная схема кодирования задачи II даст язык, принадлежащий NP.

12.7. Взаимоотношения между классами NP и Р

Всякая задача распознавания, разрешимая за полиномиальное время детерминирован-

Вопрос о взаимоотношении классов NP и Р имеет важное значение для теории NP-полных задач. Одно ным алгоритмом, разрешима 11 соотношение заключается в том, что также за полиномиальное время р vrp Всякая задача паспознава-недетерминированным алго- ьсякая задача распознава-ритмом, т.е. PCNP.ния, разрешимая за полиномиальное

" врем детерминированным алгоритмом, разрешима также за полиномиальное время недетерминированным алгоритмом. Чтобы убедиться в этом, достаточно заметить, что любой детерминированный алгоритм может быть использован в качестве стадии проверки недетерминированного алгоритма. Если II g Р и А - произвольный детерминированный алгоритм решения задачи II, то полиномиальный недетерминированный алгоритм для II можно получить, воспользовавшись А в качестве стадии проверки и игнорируя стадию угадывания. Таким образом, из II е Р, следует, что II g NP.

Один из самых значительных результатов о соотношении классов Р и NP состоит в следующем.

Теорема 12.1. Если II g NP, то существует такой полином Р, что II может быть решена детерминированным алгоритмом с временной сложностью 0(2 ""

Доказательство. Пусть А - полиномиальный недетерминированный алгоритм решения задачи II и д(гг)- полином, ограничивающий временную сложность алгоритма.

По определению класса NP, для каждого принимаемого входа длины п найдется некоторое слово-догадка (в алфавите Г символов ленты) длины не более q(n) такое, что в алгоритме А стадия проверки дает при рассматриваемом входе ответ «да» не более, чем за д(гг) шагов. Таким образом, общее число догадок, которые нужно рассмотреть, не превосходит К!"\ где \Г] (если слово-догадка короче д(п), то его можно дополнить пустыми словами и рассматривать как слово длины д(п)).

Теперь можно детерминированным образом выяснить, имеет ли алгоритм А на заданном входе длины п принимающее вычисление. Для этого достаточно на каждом из f" возможных догадок запустить детермини-398



рованную стадию проверки алгоритма А и позволить ей работать до того момента, пока она не остановится или не сделает q(n) шагов. Этот моделирующий алгоритм даст ответ «да», если ему встретится слово-догадка, приводящее к принимающему вычислению не более q(n) и ответ «нет» - в противном случае. Такой алгоритм очевидно будет детерминированным алгоритмом решения задачи П. Более того, его временная сложность равна по существу q(n) • К" и хотя это экспонента, но при подходящем выборе полинома сложность не превосходит 0(2 "). Теорема доказана.

Процесс моделирования, предложенный в доказательстве теоремы 12.1 можно в некоторой степени ускорить с помощью метода ветвей и границ или с помощью более тщательного перебора, когда избегаются ненужные слова-догадки. Тем не менее несмотря на значительное сокращение перебора в этом случае неизвестен метод, который осуществляет такое моделирование быстрее, чем за экспоненциальное время.

12.8. Полиномиальная сводимость и NP-полные задачи

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

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

миального детерминированного алгоритма несмотря на упорные усилия многих известных исследователей. Поэтому не удивляет широко распространенное мнение, что Р NP, хотя доказательство этой гипотезы отсутствует. Если Р не совпадает с NP, то различие между NP/P и Р очень существенно. Все задачи из Р могут быть решены полиномиальными алгоритмами, а все задачи из NP/P труднорешаемы. Поэтому если Р Ф NP, то для каждой конкретной задачи II е NP важно знать, какая из этих двух возможностей реализуется. Конечно, пока не доказано, что Р Ф NP, нет никаких шансов показать, что некоторая конкретная задача принадлежит классу NP/P. По этой причине цель теории

[Старт] [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]