В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 16

Рассмотрим такой параметр как размер решаемойзадачи на ЭВМ за единицу времени с помощью данного алгоритма. Тогдаизменение данного параметра при переходе к ЭВМ в 100 раз и в 1000 разбольшей производительности для различных функций временной сложностипоказан в таблице:Функциявременнойсложностиnn2n32n3nРазмер решаемойТо же на ЭВМ в 100 То же на ЭВМ в 1000задачи нараз быстрыхраз быстрыхсовременной ЭВМ засуткиN1100 N11000 N1N210 N231.6 N2N34.64 N310 N3N4N4 +6.64N4 +9.97N5N5 +4.19N5 +6.29Из таблицы видно, что в случае полиномиальных алгоритмов размер решаемойзадачи при увеличении производительности ЭВМ увеличивается намультипликативную константу, тогда как для экспоненциальных алгоритмовимеет место увеличение на аддитивную константу.Далее, полиномиальные алгоритмы обладают свойством “замкнутости”, можно комбинировать полиномиальные алгоритмы, используя один в качестве“подпрограммы” другого и при этом результирующий алгоритм будетполиномиальным.

В силу приведенных причин используется следующаятерминология: полиномиальные алгоритмы называют эффективными,полиномиально решаемые задачи называют легкорешаемые, а экспоненциальнорешаемые задачи называют труднорешаемыми. Для практики важным являетсяклассификация задач по признаку труднорешаемости, хотя следует заметить, чтоустановление легкорешаемости задачи еще не означает ее практическуюрешаемость.

Например, установление полиномиальной оценки O( n1000 ) негарантирует практической решаемости уже при начальных значениях n.89Аналогичное замечание можно сделать относительно труднорешаемости.Заметим, что труднорешаемость задачи может быть связана с тем, что еерешение настолько велико, что не может быть записано в виде выражения, длинакоторого была бы ограничена полиномом от длины входа.

Чтобы исключить этоттип труднорешаемости, рассматриваются только такие задачи, которые имеют“короткий” ответ.Рассмотрим несколько примеров.1. Пусть M= {1,2,...,n} - конечное множество и R⊆ M×M - бинарноеотношение на M.Рассмотрим задачу проверки - является ли R отношением эквивалентности.Будем задавать индивидуальную задачу матрицей A R =( aij ), i, j ∈1,n , где1, если ( i, j) ∈ Raij = 0, если ( i, j) ∉ R(3)Ясно, что R будет отношением эквивалентности тогда и только тогда, когдаматрица A R имеет единичную диагональ, симметрична и выполненосоотношениеbij ≤ aij , ∀ i, j ∈1,n(4)где ( bij )= A R2 - матрица отношения R2 . Кроме того выполнено A R2 = A R ⋅ A R ,где имеется в виду булево умножение матриц.

Ясно, что сложностьрассматриваемой задачи O( n3 ).Бинарное отношение R называется связным, если для любых i, j ∈1,nсуществует k, что выполнено iR k j .2. Бинарное отношение R называется эйлеровым, если элементы R можнотак упорядочитьR : ( i1, j1 ), ( i2, j2 ),..., ( it , jt ), t = R(5)что выполнено( j1, i2 ) ∈ R, ( j2, i3 ) ∈ R,..., ( jt−1, it ) ∈ R, ( jt , i1 ) ∈ R (6)Ясно, что эйлерово отношение является связным.Можно доказать, что связное отношение R является эйлеровым тогда итолько тогда, когда число единиц в матрице A R совпадает в i -столбце и в i строке длякаждого i ∈1,n . Это дает алгоритм сложности O( n2 ) проверяющий эйлеровостьотношения R. Ясно, что связность отношения R проверяется за O( n3 ) действий.Заметим, что здесь главным для нас является установлениеполиномиальности рассматриваемых задач, а не установление наилучшихалгоритмов.3.

Бинарное отношение R называется гамильтоновым, если элементы Мможно так упорядочить i1 , i2,..., i n , что выполнено соотношение( i1, i2 ) ∈ R, ( i2, i3 ) ∈ R,..., ( in-1, in ) ∈ R, ( in , i1 ) ∈ R (7)90В настоящее время неизвестно полиномиального алгоритма от n проверкигамильтоновости произвольного отношения R. Тривиальный алгоритм требует n! упорядочений множества М и проверки условий (7), что, конечно, превосходитпо величине любой полином от n.4. Пусть f( x1,..., xn ) - формула от булевых переменных x1,..., xn внекотором фиксированном базисе B.

Напомним, что формула f( x1,..., xn )называется выполнимой, если существует набор значений переменныхx10 ,..., xn0 ,такой, что f( x10 ,..., xn0 )=1.Формула f( x1,..., xn ) называется мультиаффинной, если она имеет вид(8)f( x1,..., xn )= ( xi1 +...+ xik + α 1 )...( xl1 +...+ xlk + α t )1t( α 1,..., α t -константы)т.е. f представляет собой конъюнкцию линейных форм.

Рассмотрим задачупроверки выполнимости мультиаффинной формулы. Ясно, что существованиевыполняющего набора для мультиаффинной формулы вводится ксуществованию решения линейной системы уравнений над полем F2 . АлгоритмГаусса дает оценку O( n3 ), поэтому рассматриваемая задача полиномиальна.Пусть формула f( x1,..., xn ) имеет конъюнктивную нормальную форму, т.е.имеет вид:αα k11k1f( x1,..., xn )= ( xi 1 ∨...∨ xiγγ kt1kt)...( xl 1 ∨...∨ xl)(9)( α i ,..., γ i - константы).Рассмотрим задачу проверки выполнимости для формул КНФ. В настоящеевремя неизвестно алгоритма полиномиальной сложности решения даннойзадачи.

Тривиальный алгоритм требует перебор 2n наборов значений( x10 ,..., xn0 ) переменных и вычисления для каждого из них значения формулы.5. Рассмотрим стандартную задачу линейного программирования: дляданных целочисленной (m ×n) -матрицы A, m -вектора b и n -вектора cа) найти n -вектор x с рациональными координатами, такой, что x ≥0 иAx=b, c T ⋅ x → min ;либоб) установить, что не существует n -вектора x, что x ≥0 и Ax=b ;либо{}в) установить, что множество c T ⋅ x : Ax = b, x ≥ 0не ограничено снизу.Хачиян Л.Г.(1979) установил, что данная задача принадлежит классу P итем самым разрешил вопрос, долго стоявший открытым.2°.

Определим теперь класс NP задач распознавания, т.е. имеющих ответ "ДА"или "НЕТ". Для того, чтобы задача I содержалась в классе NP требуется только,чтобы в случае, если I имеет ответ "ДА", то существует слово c(I), длины,91ограниченной полиномом от размера I такое, что задача с начальными даннымиc(I),I принадлежит Р . Слово c(I) называется удостоверением или догадкой длязадачи I.Рассмотрим примеры.1) Пусть дана задача проверки гамильтоновости бинарного отношения R⊆M×M на множестве M= {1,2,...,n} . Если R - гамильтоново отношение, тоудостоверением этого будет последовательность элементов M c( R) = i1 i2...

i n .Имея пару с(R), R, легко убеждаемся, проверяя соотношения (7), верно ли, что R- гамильтоново отношение. Следовательно, задача проверки гамильтоновостибинарного отношения лежит в классе NP.2) Пусть дана задача проверки выполнимости формул КНФ. Еслиf( x1,..., xn ) - выполнимая формула, то удостоверением этого будетсоответствующий выполняющий набор ( x10 ,..., xn0 ). Имея пару ( x10 ,..., xn0 ),f( x1,..., xn ), легко убедиться, верно ли, что f( x1,..., xn ) выполнима.Формализуем теперь данные идеи. Класс NP определяется через понятиенедетерминированного алгоритма. Введем понятие недетерминированноймашины Тьюринга.Схема недетерминированной машины Тьюринга:...* x1 x2 ...

xn-3 -2 -1 0 1 2УМnq1Отличие от обычной машины Тьюринга заключается в том, чтонедетерминированная машина (НТ) имеет дополнительно угадывающий модуль(УМ), который может только записывать на ленту слова из внешнего алфавита.Поскольку речь о задачах распознавания, то удобно считать, что машина имеетдва заключительных состояния qY и qN , соответствующие ответам "Да" и"НЕТ" соответственно. Работа машины имеет две стадии:1-я стадия - угадывание.

В начальный момент на ленте записано словоx= x1,..., xn - код индивидуальной задачи I, начиная с ячейки 1. В ячейке 0записан знак раздела * . Угадывающий модуль просматривает ячейку -1. ЗатемУМ пишет произвольное слово c(x) по одной букве за такт в каждой ячейке сномерами -1,-2, -3,... . В итоге 1-ой стадии конфигурацией машины будетc(x)* q1 x.2-я стадия - решение. На этой стадии недетерминированная машина работает какобычная машина Тьюринга в конфигурации c(x)* q1 x. Если машина через92конечное число шагов приходит в состояние qY , то говорим, что она принимаетконфигурацию c(x)* q1 x. Будем говорить, что недетерминированная машинапринимает x, если существует слово c(x), что конфигурация c(x)* q1 xпринимается.Определим время работы недетерминированной машины, положивtHT ( x) = t1 ( x) + t2 ( x)(если x - принимается)где t1 ( x) - время работы на стадии 1, т.е., по определению, t1 ( x) = c( x)t2 ( x) - время работы на стадии 2, т.е., по определению, t2 ( x) = tT ( c( x) * x)(Т - соответствующая (обычная) машина Тьюринга).

ОпределимtHT ( n) = max tHT ( x) .x, x = nНедетерминированная машина HТ решает задачу П за полиномиальное время,еслиtHT ( n) =O(p(n))для некоторого полинома р.Заметим, что временная функция определена только для техиндивидуальных задач x, которые принимаются машиной НТ.Определим класс задач NP как множество задач, для которых существуетнедетерминированная машина Тьюринга, принимающая за полиномиальноевремя те и только те слова, которые соответствуют индивидуальным задачам сответом "Да".Разберем теперь вопрос о взаимоотношении между введенными классамиР и NР.

Ясно, что Р ⊆ NР . Имеется много причин считать это включениестрогим, однако этот факт пока не доказан (1992).Теорема. Если задача П∈NP, то существует такой полином р, что П можетбыть решена детерминированным алгоритмом со сложностью O( 2 p( n) ), n размер П.Доказательство. Пусть НТ - недетерминированная машина Тьюринга,решающая задачу П и q(n) - полином, ограничивающий временную функциюcсложности НТ.