А.А. Сапоженко - Некоторые вопросы сложности алгоритмов (PDF) (1132758)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТим. М.В.ЛомоносоваФакультет вычислительной математики и кибернетикиНЕКОТОРЫЕ ВОПРОСЫСЛОЖНОСТИ АЛГОРИТМОВА. А. СапоженкоИздательство факультета ВМиК МГУ2001 г.АннотацияПособие является частью курса “Основы кибернетики” и посвященонекоторым вопросам сложности алгоритмов. Излагаются результатыпо алгоритмичесим трудностям синтеза схем и построения минимальных ДНФ, понятия сводимости и NP-полноты, устанавливается связьмежду временно́й сложностью вычислений на машинах Тьюринга исложностью схем.11ВведениеПособие является частью курса “Основы кибернетики” и посвящено некоторым вопросам сложности алгоритмов. Излагаются результаты по алгоритмичесим трудностям синтеза схем и построения минимальных ДНФ, понятиясводимости и 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 ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ, КЛИКА,ВЕРШИННОЕ ПОКРЫТИЕ, ПОКРЫТИЕ МНОЖЕСТВ, РАСКРАСКА.2В параграфе 7 устанавливается соотношение между схемной сложностьюи временно́й сложностью тьюринговых вычислений. Доказывается теоремаСэвиджа, о том, что всякое вычисления на машине Тьюринга, осуществляемое за T шагов, может быть смоделировано схемой из функциональныхэлементов, сложность которой по порядку не превышает T 2 .Автор выражает признательность А.И.Савельевой за помощь в подготовке текста к печати.32Алгоритмические трудности синтеза схемЭтот параграф посвящен алгоритмическим трудностям синтеза минимальных схем. Излагается один из первых математических результатов по алгоритмической сложности дискретных задач, полученный С.В.Яблонским в1959г.
[1]. Суть его состоит в том, что решение задачи построения бесконечной последовательности функций, имеющих сложную схемную реализацию, так называемыми “правильными” алгоритмами непременно связана спостроением всех функций алгебры логики. Данное изложение является переработкой статьи [2].
С целью упрощения доказательство ведется на примересхем из функциональных элементов (сокращенно, СФЭ), а не контактныхсхем как в оригинале.Определение 2.1 Множество функций Q ⊆ P2 называется инвариантным классом, если наряду с каждой функцией f ∈ Q оно содержит всефункции, получающиеся из f применением следующих трех операций:1) добавление и изъятие фиктивных переменных,2) переименование переменных (без отождествления),3) подстановка констант на места некоторых переменных.Инвариантными являются, например, классы линейных, монотонных функций.
С другой стороны, классы T0 и T1 функций, сохраняющих константы,а также класс самодвойственных функций не являются инвариантными, ибоони не замкнуты относительно подстановки констант. Тривиальными инвариантными классами называются множество всех функций P2 и пустое множество. Обозначим через Q(n) множество всех f ∈ Q, зависящих (не обязательносущественно) от переменных x1 , x2 , . . . , xn .Теорема 2.1 Последовательность1 ≤ n→∞limq2nq2n| Q(n) | не возрастает и при этом| Q(n) | ≤ 2 для всякого непустого инвариантного класса Q.Доказательство.Пусть 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, то| Q(n + 1) |≤ | Q(n) |2 .4Отсюдаq2n+1q2n| Q(n + 1) | ≤| Q(n) |.(1)qnИз (1) вытекает невозрастание последовательности 2 | Q(n) |. Покажем, чтоона ограничена.
Если Q не пусто, тоq√ n√n2n2n1=1 ≤ 2 | Q(n) | ≤22 = 2.(2)Следовательно, предел последовательностичен в сегменте [1, 2].qq2n| Q(n) | существует и заклю2nИз теоремы 2.1 следует, что limn→∞ 2 | Q(n) | можно представить в виде 2σ , где 0 ≤ σ ≤ 1. Число σ называется характеристикой инвариантногокласса Q. Иногда мы будем указывать его в качестве индекса при Q илиQ(n). Из сказанного выше следует, чтоn (1+² )n| Qσ (n) |= 2σ2, где ²n → 0 при n → ∞.(3)Следствие 2.1 Если инвариантный класс Qσ не совпадает с P2 , то σ < 1.В самом деле, при некотором фиксированномq m существует функция2ng(x1 , .
. . , xm ) ∈/ Q. Так как последовательность| Q(n) | не возрастает, тоqlimn→∞2nq| Q(n) | ≤2mОтсюда вытекает утверждение.m−m| Q(m) | ≤ (22 − 1)2< 2.2Теорема 2.2 Cуществует инвариантный класс Q с характеристикой σ =1.2Доказательство.Рассмотрим класс Q, состоящий из функций f (x1 , . . . , xn ), представимых ввиде(4)f (x1 , . . .
, xn ) = l(x1 , . . . , xn )&g(x1 , . . . , xn ),где l — линейная функция а g — произвольная функция из P2 , любая существенная переменная которой является существенной переменной функции l.Легко видеть, что Q является инвариантным классом.Нижняя оценка | Q(n) |. Выберем линейную функцию l в (4) равнойx1 ⊕. .
.⊕xn . Пусть B n,1 — множество двоичных наборов длины n с нечетнымчислом координат, равных 1. Ясно, что Nl = B n,1 и |B n,1 | = 2n−1 . Среди5n−1функций g(x1 , . . . , xn ) ∈ P2 найдется множество G из 22функций попарноотличающихся друг от друга на множестве B n,1 . Ясно, что число функцийn−1n−1вида (4) с l = x1 ⊕ . . . ⊕ xn и g ∈ G равно 22 . Отсюда 22≤| Q(n) |.Верхяя оценка | Q(n) |. При фиксированной функции l = xi1 ⊕ . . . ⊕ xirr−1n−1имеется не более 22≤ 22различных функций f ∈ Q(n).
Число линейных функций, зависящих от переменных x1 , . . . , xn , равно 2n+1 . Поэтомуn−1| Q(n) |≤ 2n+1 22 . Таким образом22n−1n−1≤| Q(n) |≤ 2n+1 22Отсюда.qlimn→∞2n| Q(n) | = 21/2 .Тем самым инвариантный класс Q с характеристикой σ = 1/2 построен. 2Упражнение 1. Доказать, что класс линейных функций является инвариантным с характеристикой 0.Упражнение 2. Доказать, что класс монотонных функций является инвариантным с характеристикой 0.
(Указание: Воспользоваться тем, что число монотонных функций, зависящих от переменных x1 , x2 , . . . , xn , не превосnходит n(dn/2e) ). Возникает следующий вопрос. Можно ли для любого σ такого,что 0 ≤ σ ≤ 1 построить инвариантный класс с характеристикой σ?Ответ на этот вопрос заключается в следующем. При σ = 1 таковым является множество P2 всех булевых функций, а при σ ∈ [0, 1) ответом являетсятеорема, формулировку которой мы здесь приведем:Теорема 2.3 (С.В.Яблонский [2]) Для любого σ ∈ [0, 1) существует континуум попарно различных инвариантных классов Q с характеристикой σ.Обозначим через L(f ) сложность минимальной схемы из функциональных элементов, реализующей функцию f , и пусть L(n) = maxf ∈P2 (n) L(f ),LQ (n) = maxf ∈Q(n) L(f ).
В [3] доказана следующаяТеорема 2.4 (О.Б.Лупанов (см.[3]))L(n) =2n(1 + δn ),nгде δn → ∞ при n → ∞.Cледующая теорема также принадлежит О.Б.Лупанову6(5)Теорема 2.5 Если Q — инвариантный класс с характеристикой σ, тоLQ (n) ≤ σ2n(1 + ∆n ),n(6)где ∆n → 0 при n → ∞.Доказательство.Пусть k — целое число, 1 ≤ k ≤ n.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
