А.А. Сапоженко - Некоторые вопросы сложности алгоритмов

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТим. М.В.ЛомоносоваФакультет вычислительной математики и кибернетикиНЕКОТОРЫЕ ВОПРОСЫСЛОЖНОСТИ АЛГОРИТМОВА. А. СапоженкоИздательство факультета ВМиК МГУ2001 г.УДК 519.95Пособие является частью курса “Основы кибернетики"и посвящено некоторым вопросам сложности алгоритмов. Излагаются результаты по алгоритмичесим трудностям синтеза схем и построения минимальных ДНФ, понятия сводимости иNP-полноты, устанавливается связь между временно́й сложностью вычислений на машинах Тьюринга и сложностью схем.1 ВведениеПособие является частью курса “Основы кибернетики"и посвящено некоторым вопросам сложности алгоритмов.

Излагаютсярезультаты по алгоритмичесим трудностям синтеза схем и построения минимальных ДНФ, понятия сводимости и NPполноты, устанавливается связь между сложностью схем и временно́й сложностью вычислений на машинах Тьюринга.Параграф 2 посвящен алгоритмическим трудностям синтеза минимальных схем. Излагается один из первых математических результатов по алгоритмической сложности дискретных задач, полученный С.В.Яблонским в 1959г. Содержательныйсмысл его состоит в том, что некоторые задачи синтеза схем не могут быть решены без перебора.В параграфе 3 дается понятие локального алгоритма, введенное Ю.И.Журавлевым и излагаются некоторые результатыиз теории локальных алгоритмов. В частности, доказывается неразрешимость в классе локальных алгоритмов произвольногоконечного индекса задачи о вхождении конъюнкции из сокращенной ДНФ булевой функции в хотя бы в одну минимальнуюДНФ этой функции.Параграфы 4 – 6 посвящены подходу к вопросу о сложности комбинаторных задач, основанному на понятии полиномиальной сводимости и теореме Ст.

Кука. Суть этого подхода в том, что существует большой класс так называемых N P -полныхзадач, ни для одной из которых пока (к 2001г.) не удалось найти полиномиального алгоритма. Все эти задачи эквивалентнымежду собой в том смысле, что либо каждая из них решается эффективно, либо ни одна из них такого решения не имеет.Таким образом, принадлежность некоторой задачи этому классу является некоторым доводом в пользу того, что она неимеет эффективного решения.В параграфе 4 формулируются понятия полиномиальной сводимости, детерминированных и недетерминированных вычислений, N P -полноты и доказывается теорема Кука о том, что всякая задача из класса N P полиномиально сводится кзадаче о выполнимости конъюнктивных нормальных форм (КНФ).Параграф 5 посвящен некоторым разновидностям задач о выполнимости КНФ.

Доказывается принадлежность задачиВЫПОЛНИМОСТЬ классу N P , полиномиальность задачи 2- ВЫПОЛНИМОСТЬ и N P -полнота задачи 3-ВЫПОЛНИМОСТЬ .В параграфе 6 расширяется список N P -полных задач. Доказывается N P -полнота задач 0-1 ЦЕЛОЧИСЛЕННОЕПРОГРАММИРОВАНИЕ, КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ, ПОКРЫТИЕ МНОЖЕСТВ, РАСКРАСКА.В параграфе 7 устанавливается соотношение между схемной сложностью и временно́й сложностью тьюринговых вычислений.

Доказывается теорема Сэвиджа, о том, что всякое вычисления на машине Тьюринга, осуществляемое за T шагов,может быть смоделировано схемой из функциональных элементов, сложность которой по порядку не превышает T 2 .Автор выражает признательность А.И.Савельевой за помощь в подготовке текста к печати.2 Алгоритмические трудности синтеза схемЭтот параграф посвящен алгоритмическим трудностям синтеза минимальных схем. Излагается один из первых математических результатов по алгоритмической сложности дискретных задач, полученный С.В.Яблонским в 1959 г. [1].

Суть егосостоит в том, что решение задачи построения бесконечной последовательности функций, имеющих сложную схемную реализацию, так называемыми “правильными"алгоритмами непременно связано с построением всех функций алгебры логики.Данное изложение является переработкой части статьи [2]. С целью упрощения доказательство ведется на примере схем изфункциональных элементов (сокращенно СФЭ), а не контактных схем, как в оригинале.Определение 2.1 Множество функций Q ⊆ P2 называется инвариантным классом, если наряду с каждой функциейf ∈ Q оно содержит все функции, получающиеся из f применением следующих трех операций:1) добавление и изъятие фиктивных переменных,2) переименование переменных (без отождествления),3) подстановка констант на места некоторых переменных.Инвариантными являются, например, классы линейных, монотонных функций.

С другой стороны, классы функций T0 и T1 ,сохраняющих соответственно константы 0 и 1, а также класс самодвойственных функций не являются инвариантными, ибоони не замкнуты относительно подстановки констант. Тривиальными инвариантными классами называются множество всехфункций P2 и пустое множество. Обозначим через Q(n) множество всех f ∈ Q, зависящих (не обязательно существенно)от переменных x1 , x2 , . . . , xn .Теорема 2.1 Для всякого непустого инвариантного класса Q.

последовательностьэтом1 ≤ limn→∞2np2np|Q(n)| не возрастает и при|Q(n)| ≤ 2.Доказательство.Пусть n ≥ 0 и f (x1 , . . . , xn , xn+1 ) — произвольная функция из Q(n + 1). Из разложенияf (x1 , . . . , xn , xn+1 ) = xn+1 f (x1 , . .

. , xn , 1) ∨ x̄n+1 f (x1 , . . . , xn , 0)следует, что функция f полностью определяется парой своих подфункций f (x1 , . . . , xn , 1) и f (x1 , . . . , xn , 0). Посколькупоследние также принадлежат классу Q, имеем2|Q(n + 1)| ≤ |Q(n)| .Отсюдаppn|Q(n + 1)| ≤ 2 |Q(n)|.(1)p2nИз (1) вытекает невозрастание последовательности|Q(n)|. Покажем, что она ограничена. Если Q не пусто, то√ npp√nn2n2n1=1 ≤ 2 |Q(n)| ≤ 2 |32 (n)| =22 = 2.(2)pnСледовательно, предел последовательности 2 |Q(n)| существует и заключен в сегменте [1, 2].2pnИз теоремы 2.1 следует, что limn→∞ 2 |Q(n)| можно представить в виде 2σ , где 0 ≤ σ ≤ 1.

Число σ называетсяхарактеристикой инвариантного класса Q. Иногда мы будем указывать его в качестве индекса при Q или Q(n). Изсказанного выше следует, чтоn|Qσ (n)| = 2σ2 (1+n ) , где n → 0 при n → ∞.(3)2n+1Следствие 2.1 Если инвариантный класс Qσ не совпадает с P2 , то σ < 1.2/ Q. Так как последовательностьp В самом деле, при некотором фиксированном m существует функция g(x1 , . . . , xm ) ∈|Q(n)| не возрастает, тоppm−mnmlim 2 |Q(n)| ≤ 2 |Q(m)| ≤ (22 − 1)2< 2.2nn→∞2Отсюда вытекает утверждение.Теорема 2.2 Cуществует инвариантный класс Q с характеристикой σ = 21 .Доказательство.Рассмотрим класс Q, состоящий из функций f (x1 , .

. . , xn ), представимых в видеf (x1 , . . . , xn ) = l(x1 , . . . , xn )&g(x1 , . . . , xn ),(4)где l — линейная функция, а g — произвольная функция из P2 , у которой каждая существенная переменная являетсясущественной переменной функции l. Легко видеть, что Q является инвариантным классом.Нижняя оценка |Q(n)|. Выберем линейную функцию l в (4) равной x1 ⊕ . . .

⊕ xn . Пусть B n,1 — множество двоичныхнаборов длины n с нечетным числом координат, равных 1. Через Nf обозначим множество наборов, обращающих функциюn−1f в единицу. Ясно, что Nl = B n,1 и |B n,1 | = 2n−1 . Среди функций g(x1 , . . . , xn ) ∈ P2 найдется множество G из 22функций попарно отличающихся друг от друга на множестве B n,1 . Ясно, что число функций вида (4) с l = x1 ⊕ . . . ⊕ xn иn−1n−1g ∈ G равно 22 . Отсюда 22≤ |Q(n)|.r−1n−1Верхняя оценка |Q(n)|. При фиксированной функции l = xi1 ⊕ . . . ⊕ xir имеется не более 22≤ 22различныхфункций f ∈ Q(n). Число линейных функций, зависящих от переменных x1 , . .

. , xn , равно 2n+1 . Поэтому |Q(n)| ≤n−12n+1 22 . Таким образомn−1n−122≤ |Q(n)| ≤ 2n+1 22 .Отсюдаlimn→∞2np|Q(n)| = 21/2 .Тем самым инвариантный класс Q с характеристикой σ = 1/2 построен.2Упражнение 1. Доказать, что класс линейных функций является инвариантным с характеристикой 0.Упражнение 2.

Доказать, что класс монотонных функций является инвариантным с характеристикой 0. (Указание:nВоспользоваться тем, что число монотонных функций, зависящих от переменных x1 , x2 , . . . , xn , не превосходит n(dn/2e) ).Возникает следующий вопрос. Можно ли для любого σ такого, что 0 ≤ σ ≤ 1 построить инвариантный класс с характеристикой σ?Ответ на этот вопрос заключается в следующем. При σ = 1 таковым является множество P2 всех булевых функций, апри σ ∈ [0, 1) ответом является теорема, формулировку которой мы здесь приведем:Теорема 2.3 (С.В.Яблонский [2]) Для любого σ ∈ [0, 1) существует континуум попарно различных инвариантныхклассов Q с характеристикой σ.Обозначим через L(f ) сложность минимальной схемы из функциональных элементов, реализующей функцию f , и пустьL(n) = max L(f ), LQ (n) = max L(f ).

В дальнейшем используетсяf ∈P2 (n)f ∈Q(n)Теорема 2.4 (О.Б.Лупанов (см.[3]))L(n) =2n(1 + δn ),nгде δn → 0 при n → ∞.Cледующая теорема также принадлежит О.Б.Лупанову3(5)Теорема 2.5 Если Q — инвариантный класс с характеристикой σ, тоLQ (n) ≤ σ2n(1 + ∆n ),n(6)где ∆n → 0 при n → ∞.Доказательство.Пусть k — целое число, 1 ≤ k ≤ n. В силу (3) имеемk|Qσ (k)| = 2σ2(1+k ),(7)где k → 0 при k → ∞.

Можно считать, что функции f (x1 , x2 , . . . , xk ) из Q(k) пронумерованы числами от 1 до mk ,где mk = |Q(k)|. Функции fi поставим в соответствие двоичный вектор (τ1i , τ2i , . . . , τli ) длины l = dlog mk e, являющийсядвоичным разложением числа i − 1, i = 1, . . . , mk .

Этот вектор назовем кодом функции f (x1 , x2 , . . . , xk ). В силу (7) имеемl = dlog mk e = σ2k (1 + k ).Покажем, как вычислить значение произвольной функции f (x1 , x2 , . . . , xn ) из Q(n) на произвольном наборе (α1 , α2 , . . . , αn ).Разложим f (x1 , x2 , . . . , xn ) по последним n − k переменным:_αk+1nf (x1 , x2 , . . . , xn ) =xk+1, . . . , xα(8)n &f (x1 , . . . , xk , αk+1 , .

. . , αn ).(αk+1 ,...,αn )Ясно, что функция f однозначно определяется набором из 2n−k своих подфункций f (x1 , . . . , xk , αk+1 , . . . , αn ), каждая изкоторых принадлежит множеству Q(k), а значит, имеет свой код (τ1 , . . . , τl ). Этот код однозначно определяется набором(αk+1 , . . . , αn ). Следовательно, для определения кода достаточно вычислить l функций от n − k переменных. По коду(τ1 , . . .

, τl ) подфункции однозначно восстанавливается вектор (β1 , . . . , β2k ) ее значений. Для этого достаточно вычислить 2kбулевых функций, зависящих от l переменных. Далее, по вектору значений подфункции f (x1 , . . . , xk , αk+1 , . . . , αn ) и вектору(α1 , . . . , αk ) значений переменных x1 , . . . , xk , определяется значение функции f (α1 , . . . , αn ).В соответствии с вышесказанным можно следуюшим образом построить схему Sf , реализующую функцию f и состоящуюиз трех блоков (см.

рис. 2.1).Рис. 2.1Блок A вычисляет код (τ1i , . . . , τli ) подфункции f (x1 , . . . , xk , αk+1 , . . . , αn ) по значениям αk+1 , . . . , αn переменных xk+1 , . . . , xn ,т.е. вычисляет l функций этих переменных.Положив k = d 21 log2 ne, в силу (5) получаем, что для сложности L(A) блока A выполнено следующее:L(A) ≤ l2n−k2n−k2n(1 + δn−k ) ≤ σ2k (1 + k )(1 + δn−k ) ∼ σ .n−kn−kn(9)Блок B вычисляет по коду подфункции вектор ее значениий, т.е. вычисляет 2k булевых функций, зависящих от l переменных.