В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 19
Описание файла
PDF-файл из архива "В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций)", который расположен в категории "". Всё это находится в предмете "теория интеллектуальных систем" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 19 страницы из PDF
R iлогически эквивалентно формуле КНФ, имеющей самое большее однопеременное с отрицанием в каждой дизъюнкции.4) Каждое отношение R i , i ∈1,m из S слабо отрицательно, т.е. R iлогически эквивалентно формуле КНф, инеющей самое большее одно переменноебез отрицания в каждой дизъюнкции.5) Каждое отношение R i , i ∈1,m из S мультиаффинно, т.е. R i логическиэквивалентно формуле, являющейся конъюнкцией линейных форм над полем F2 .6) Каждое отношение R i , i ∈1,m из S биюнктивно, т.е. R i логическиэквивалентно формуле КНФ, имеющей самое большее вхождения 2-х переменныхв каждой дизъюнкции.2°. Установим теперь NP -трудность некоторых задач, уже встречавшихся в курсематематической логики.
Рассмотрим следующие задачи о булевых функциях.1) РАВНОВЕРОЯТНОСТЬ БУЛЕВОЙ ФУНКЦИИ. Для данной булевойфункции f ( x1,..., xn ) , заданной в КНФ, узнать, является ли она равновероятной(т.е. верно ли f = 2n−1 ).2) ЛИНЕЙНОСТЬ БУЛЕВОЙ ФУНКЦИИ. Для данной булевой функцииf ( x1,..., xn ) , заданной в КНФ, узнать, является ли она линейной.3) СУЩЕСТВЕННОСТЬ ПЕРЕМЕННОГО. Для данных булевой функцийf ( x1,..., xn ) в КНФ и целого числа k узнать, является ли переменное xkсущественным для f.4) ФУНКЦИОНАЛЬНАЯ ПОЛНОТА.
Для данной булевой функцииf ( x1,..., xn ) в КНФ выяснить, образует ли f функционально полную систему(является ли f шефферовой).Утверждение 5. Задачи 1) - 4) являются NP -труд-ными.Доказательство.1. Пусть f ( x1,..., xn ) - произвольная индивидуальная задача ВЫП, гдеf ( x1,..., xn ) = D1D2... Dm , Di - дизъюнкции. Определим функциюf *( x1,..., xn , y) = D1... Dm ∨ y , где y - новое переменное.Имеемf *( x1,..., xn , y) = D1...
Dm ∨ y = ( D1 ∨ y)...( Dm ∨ y)и, значит, КНФ для функции f * строятся по функции f за полиномиальное время.Легко видеть, что104f * = f + 2n , где f - вес функции f. Значит, f * равновероятна ⇔ f невыполнима.Ясно, что условие Задача 1)∈P ⇒ ВЫП∈P, что означает Задача 1)∈NPH.2. Пусть f ( x1,..., xn ) - произвольная индивидуальная задача ВЫП.Определим функцию f * ( x1,..., x n , y1, y2 ) = f ( x1,..., x n ) y1 ∨ y2 , где y1, y2 новые переменные. Ясно, что КНф для функции f * строится по f заполиномиальное время. Легко видеть, что f * линейна ⇔ f не выполнима иусловие Задача 2)∈P влечет ВЫП∈P, что означает Задача 2)∈NPH.3.
Пусть f ( x1,..., xn ) - произвольная индивидуальная задача ВЫП.Образуем функцию f * ( x1,..., x n , y) = f ( x1,..., x n ) y , где y - новое переменное.Ясно, что y - существенно для f * ⇔ f - выполнима. Следовательно,Задача3)∈P ⇒ ВЫП∈P и поэтому Задача 3)∈NPH.4. Пусть f ( x1,..., xn ) - произвольная индивидуальная задача ВЫП.Образуем функцию f * ( x1,..., x n , y1, y2, y3 ) == f ⋅ y1 y2 ∨ y3 .
Ясно, что КНФ для f * строится по f за полиномиальное время.Функция f * образует функционально полную систему ⇔ f выполнима.Действительно, если f не выполнима, то f * ≡ y3 и f * не является функциональнополной. Если f выполнима, то пусть x10 ,..., x n0 - выполняющий набор. Тогдаимеем00f * ( x10 ,..., x n0 ,001, , ) = f * ( x1 ,..., x n ,110, , ) =1f * ( x10 ,..., x n0 ,000, , ) = f * ( x10 ,..., x n0 ,001, , ) =1Отсюда следует не самодвойственность и не линейность функции f *. Очевидно,что f * не сохраняет нуль, не сохраняет единицу и не монотонна. Значит, функцияf * удовлетворяет критерию Шеффера функциональной полноты. Следовательно,условиеЗадача 4)∈P ⇒ ВЫП∈P и поэтому Задача 4)∈NPH. Утверждениедоказано.Замечание. Легко убедиться, что отрицание задачи 2), задача 3) лежат вклассе NP и поэтому они NP -полны. Неизвестно, верно ли это для задач 1) и4).
Очевидно, что при табличном задании булевых функций рассмотренныезадачи имеют полиномиальную сложность.З°. Разберем еще одно важное понятие, относящееся к обсуждаемому кругувопросов. Рассмотрим задачу ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК, которая, какотмечалось выше, является NP -полной. Пусть c1,..., cn , K - натуральные числа испрашивается, существуют ли такие целые x1,..., x n ≥0, что выполненоn∑ j =1 c j x j= K.Приведем один алгоритм решения данной задачи. Для индивидуальной задачиЦР( c1,..., cn , K ) построим ориентированный граф G( c1,..., cn , K )=(V,E), гдеV = {0,1,...,K } ,105{}E = (m, k),0 ≤ m < k ≤ K и k − m = c j для некоторого j ≤ n .Значит, граф G имеет K+1 вершин и O(nK) дуг.Утверждение 6.
В графе G( c1,..., cn , K ) имеется путь из 0 в K тогда итолько тогда, когда индивидуальная задача ЦР( c1,..., cn , K ) имеет решение.Доказательство. Пусть (0 ≡ i0 , i1,..., i m ≡ K ) - нужный путь в графе G.Рассмотрим набор чисел ( s1,... sm ) == ( i1 − i0 ,..., im − im−1 ) . Все эти числа содержатся среди чисел {c1,..., cn }согласно определению графа G.
Кроме того, имеемn∑ i=1 si= K . Отсюда следует,что уравнениеn∑ j =1 c j x j=Kразрешимо в неотрицательных числах, причем x j равно числу появлений c j впоследовательности ( s1,... sm ) . Обратно, еслиn∑ j =1 c j x j= K длянеотрицательных целых чисел x1,..., x n , то можно восстановить некоторый путьиз 0 в K в графе G, если положить( s1,... sm ) = ( c1... c1 c2... c2...
cn ... cn123 123 12 3x1 раз x2 разxn рази пусть из 0 в K имеет вид (0 ≡ i0 , i1,..., i m−1, i m ≡ K ) , гдеi1 = s1, i2 = s1 + s2,..., im = s1 +...+ sm . Утверждение доказано.Утверждение 7. Любая индивидуальная задача ЦР может быть решена заO(nK) действий.Доказательство. По данным c1,..., cn , K строим граф G за O(nK) действий.Затем за O(nK) действий проверяем существует ли путь из 0 в K, используяспособ пометок: вершину 0 помечаем 0, вершины, достижимые из 0 за 1 шаг,помечаем 1 и т.д. Если K получает пометку, то задача разрешима, если нет, нонеразрешима. Утверждение доказано.Приведенный результат показывает, что NP -полная задачаЦЕЛОЧИСЛЕННЫЙ РЮКЗАК решается с помощью алгоритма с временнойсложностью O(nK) - полиномиального и, следовательно, доказано, что P = NP иможно считать ненужным предыдущее и последующее обсуждение теории NP полноты.
Дело в том, что оценка O(nK) не является полиномиальной функцией отдлины входа, т.к. целые числа в экономном кодировании должны задаваться вдвоичной системе счисления. В то же время приведенный результат важен, т.к. онпоказывает, что NP -полные задачи имеют разную "сложность".Для задач с числовыми параметрами введем следующие определения. ПустьI - индивидуальная вычислительная задача, т.е. с числовыми параметрами.Обозначим через num ( I ) - наибольшее целое число, появляющееся в I.Определение. Пусть А - вычислительная задача иf :N→N - числовая функция. Обозначим через A f подзадачу задачи А, в которойберутся индивидуальные задачи I, для которых выполнено106num( I ) ≤ f ( | I | )Говорят, что задача А сильно NP -полна, если для некоторго полинома p(n) задачаA p является NP -полной.Замечание.
Можно показать, что задачи КЛИКА, ГАМИЛЬТОНОВ ЦИКЛявляются сильно NP -полными, а задачи (0,1)-РЮКЗАК и ЦЕЛОЧИСЛЕННЫЙРЮКЗАК не являются таковыми.Определение. Алгоритм а для задачи А называют псевдополиномиальным,если он решает любую индивидуальную задачу I∈A за время, ограниченноеполиномом (двух переменных) от | I | и num ( I ). Значит, алгоритм со сложностьюO(nK) для задачи ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК являетсяпсевдополиномиальным (Ясно, что для индивидуальной задачи I ЦР num ( I )=K ).Отметим, что сильная NP -полнота задачи делает маловероятнымсуществование псевдополиномиального алгоритма точно также, как NP -полнотазадачи делает маловероятным существование полиномиального алгоритма.Утверждение 8.
Если P = NP, то ни для одной сильно NP -полной задачи несуществует псевдополиномиального алгоритма.Доказательство. Пусть А - сильно NP -полная задача. Значит, длянекоторого полинома p(n) задача A p является NP -полной. Далее, пусть для Асуществует псевдополиномиальный алгоритм a, который решает любуюиндивидуальную задачу I∈А за время q( | I | ,num ( I )) для некоторого полинома qот двух переменных. Тогда очевидно, что алгоритм a решает NP -полную задачуA p за время q(n,p(n)) - что является полиномиальной оценкой.
Полученопротиворечие при P = NP. Утверждение доказано.107§ 17. Сложность алгоритмов, использующих рекурсию1°. Рекурсия является важным и очень общим алгоритмическим приемомдля построения эффективных алгоритмов. Данный прием заключается в решениизадачи путем сведения ее к одной или нескольким подзадачам за счет разбиенияисходной задачи. Используя рекурсию, часто можно достаточно простопредставить и записать алгоритмы.
Многие языки программирования (Алгол,PL/1, Паскаль, но не ФОРТРАН) допускают рекурсивные процедуры. Для многихпрактически важных задач лучшие оценки сложности дают алгоритмы,использующие рекурсию. Рассмотрим несколько примеров.1. Сортировка чисел. Дана последовательность x1 , x2 ,..., xn натуральныхчисел.
Требуется путем попарных сравнений чисел упорядочить ее, т.е.представить в видеxi1 , xi2 ,..., xin ,(1)причемxi1 ≤ xi2 ≤ ...≤ xin .Ясно, что данная задача может быть решена с помощью алгоритма, которыйпопарными сравнениями находит наименьший элемент последовательности иставит его в начало результирующей последовательности и затем повторяетданный шаг. Легко видеть, что такой алгоритм требует O( n2 ) попарныхсравнений в худшем случае. Предложим для данной задачи рекурсивныйалгоритм. Пусть n= 2k .При k=1 алгоритм упорядочивает последовательность одним сравнением.Пусть для k алгоритм определен.
Тогда при k +1 алгоритм работает так:1. Последовательность x1 , x2 ,..., x2k +1 разбивается на две длины 2k :x1 , x2 ,..., x2k и x2k +1 ,..., x2k +1 .2. К обеим последовательностям длины 2k применяется построенныйалгоритм и получаем две упорядоченные последовательности: x1′ , x2′ ,..., x2′ k иx2′ k +1 ,..., x2′ k +1 .3. Осуществляется слияние двух полученных упорядоченныхпоследовательностей сравнением их наименьших элементов x1′ и x2′ k +1 ипомещением наименьшего в начало результирующей последовательности.Пусть n ≠ 2k .