А.А. Сапоженко - Некоторые вопросы сложности алгоритмов (1158759)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТим. М.В.ЛомоносоваФакультет вычислительной математики и кибернетикиНЕКОТОРЫЕ ВОПРОСЫСЛОЖНОСТИ АЛГОРИТМОВА. А. СапоженкоИздательство факультета ВМиК МГУ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 переменных.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
