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

В силу (5) получаем, что сложность L(B) блока B удовлетворяет неравенствуkL(B) ≤ 2k√ 2σ(1+k )22l(1 + δl ) ≤ 2k(1 + δl ) = O 2 n .klσ(1 + k )24(10)Блок C по столбцу значений подфункции f (x1 , . . . , xk , αk+1 , . . . , αn ) и вектору (α1 , . . . , αk ) вычисляет f (α1 , .

. . , αk , αk+1 , . . . , αn )Тем самым он вычисляет некоторую булеву, зависящую от k + 2k переменных. В силу (5) получаем, для сложности L(C)блока C следующее неравенствоk√ 22 +k(1 + δ2k +k ) = O 2 n .L(C) ≤ k(11)2 +kИз (9) — (11) вытекает, что√ 2nL(Sf ) ≤ L(A) + L(B) + L(C) ≤ σ+O 2 n .nОтсюда следует утверждение.2Определение 2.2 Функцию fn (x1 , . . .

, xn ) назовембулевыхсложной, если L(fn ) = L(n). Бесконечнуюпоследовательностьфункцийf1 (x1 ), f2 (x1 , x2 ), . . . ,fn (x1 , . . . , xn ), . . . ,назовем сложной, если для любого N существует n ≥ N такое, чтофункция fn (x1 , . . . , xn ) является сложной.Определение 2.3 Алгоритм,строящий бесконечную последовательность булевых функций∞fi (x1 , . .

. , xi ) i=1 изP2 называется правильным, если он строит все функции минимального инвариантного класса, содержащего этупоследовательность.Теорема 2.6 (С.В.Яблонский) Любой правильный алгоритм, строящий сложную последовательность функций fi (x1 , . . . , xi )из P2 строит все множество P2 .Доказательство.∞Предположим противное.

Тогда последовательность fi (x1 , . . . , xi ) i=1 содержится в некотором инвариантном классе Qσ 6=P2 . При этом σ < 1 в силу cледствия 2.1. По теореме 2.4 для любой функции g ∈ Qσ (n) можно построить СФЭ Sgтакую, что L(Sg ) ≤ σ(1 + ∆n ) 2n /n, где ∆n → 0 при n → ∞. Но для сколь угодно большого n класс Qσ содержит функциюf (x1 , . . . , xn ), для которой L(f ) = L(n).

В силу (5) имеем L(f ) = (1 + δn )2n /n, где δn → 0 при n → ∞. При достаточнобольших n приходим к противоречию.2Замечание 2.1 Теорема 2.6 остается, очевидно, справедливой, если назвать сложной такую последовательность, которая содержит бесконечную подпоследовательность функций fik (exik ), удовлетворяющих условию L(fik ) ≥ (1 −ik )2ik /ik , где ik → ∞ при k → ∞ (т.е. подпоследовательность не “самых сложных", а “почти самых сложных"функций).Список литературы[1] С.В.Яблонский, О невозможности элиминации перебора всех функций из P2 при решении некоторых задач теориисхем// ДАН СССР, 124, 1, 1959, C.44-47.[2] С.В.Яблонский, Об алгоритмических трудностях синтеза минимальных контактных схем// В сб. Проблемы кибернетики, М: Наука, Вып.

2, 1959, С.75-121.[3] О.Б.Лупанов, Асимптотические оценки сложности управляющих систем, Изд-во МГУ, 1984, 137 C.53 Локальные алгоритмыВ параграфе дается понятие локального алгоритма, введенное Ю.И.Журавлевым (см. [1] и [2]), и излагаются некоторыерезультаты из теории локальных алгоритмов. В частности, доказывается неразрешимость в классе локальных алгоритмовпроизвольного конечного индекса задачи о вхождении конъюнкции из сокращенной ДНФ булевой функции в хотя бы водну минимальную ДНФ этой функции.В первой части параграфа дается определение локального алгоритма и доказываются утверждения о распознаваниисвойств конъюнкций входить в тупиковые ДНФ. Показано, что распознавание свойства конъюнкции “входить во все тупиковые"или “входить хотя бы в одну тупиковую ДНФ"произвольной функции можно осуществить с помощью локальногоалгоритма ограниченного индекса, т.е.

на основе информации о строении некоторой окрестности ограниченного порядкарассматриваемой конъюнкции (см. следствия 3.1 и 3.2). Во второй части доказывается, что свойство конъюнкции входитьхотя бы в одну минимальную ДНФ не распознается в общем случае алгоритмами любого конечного индекса (следствие 3.4).Изложение ведется с некоторыми упрощениями по сравнению с [2].Определения и общие сведения.Ниже речь идет о локальных алгоритмах, предназначенных для упрощения ДНФ.

Входом алгоритма является сокращенная ДНФ. Алгоритм расставляет отметки над конъюнкциями. Отметки несут информацию о выполнении или невыполнениинекоторых свойств. Вычисление отметок носит локальный характер в том смысле, что значение пометок является однозначной функцией окрестности рассматриваемой конъюнкции и пометок конъюнкций из этой окрестности. Понятие окрестностиконъюнкции в ДНФ определяется по индукции.Определение 3.1 Окрестность S0 (K, D) нулевого порядка конъюнкции K в ДНФ D определяется равенствомS0 (K, D) = {K}.Пусть окрестность Sr (K, D) порядка r ≥ 0 конъюнкции K в ДНФ D уже определена.

Тогда окрестность порядка r + 1конъюнкции K в ДНФ D определяется равенствомSr+1 (K, D) = {L ∈ D : ∃K ∈ Sr (K, D) : NK ∩ NL 6= ∅}.Пример. Пусть D = Dfсокр = K1 ∨∨ K2 ∨ K3 ∨ K4 ,гдеK1 = x̄1 x̄2 ,S0 (K2 , D) = K2 , S1 (K2 , D) = {K1 , K2 , K3 } иK2 = x̄1 x3 ,K3 = x2 x3 ,K4 = x1 x2 .Sr (K2 , D) = {K1 , K2 ,K3 , K4 }, при r ≥ 2.Ниже рассматриваются следующиесвойства конъюнкций K:10 K входит во все тупиковые ДНФ функции f .20 K входит в хотя бы в одну тупиковую ДНФфункции f .30 K входит в хотя бы в одну минимальнуюДНФ функции f .Значения функции ϕi , вычисляющей пометку,относящуюся к свойству i = 1, 2, 3, выбираются следующим образом: 1, если свойство выполнено,0, если свойство не выполнено,ϕi (K, Sr (K, D)) =−, если неизвестно, выполнено ли свойство.Тогда (см.

рис. 3.1)Рис.3.1Функции ϕi обладают следующим свойством локальности: для любых двух ДНФ D и D0 , содержащих слагаемое K,выполняется равенствоϕi (K, Sr (K, D)) = ϕi (K, Sr (K, D0 ))(12)6Равенство окрестностей подразумевает не только совпадение окрестностей как множеств, но и равенство пометок надсоответствующими конъюнкциями.Локальный алгоритм индекса r преобразует сокращенную ДНФ без пометок (или, что то же, с пометками вида “ − ”)в ДНФ, состоящую из тех же конъюнкций, но с пометками, несущими информацию о вхождении их в ДНФ того или иноготипа.

При вычислении пометки над очередной конъюнкцией алгоритм использует информацию о ее окрестности порядка rс учетом уже вычисленных пометок над конъюнкциями из этой окрестности. Алгоритм работает следующим образом:1. Нумеруются некоторым образом конъюнкции K из Dfсокр . Все пометки над конъюнкциями в начальный момент равны“ − ”.2. Выбирается первая по номеру конъюнкция K.

Вычисляются одна или несколько функций ϕi , i = 1, 2, 3, по паре(K, Sr (K, D)). В результате вычисления либо хотя бы одна пометка изменяется, либо нет. В первом случае заново нумеруемконъюнкции и продолжаем процесс с учетом новых пометок. Во втором случае переходим к следующей по номеру конъюнкции. Если номер конъюнкции оказался последним, и ни одна отметка не изменилась после очередной перенумерации,алгоритм заканчивает работу. Результатом является ДНФ Dfсокр с теми пометками над конъюнкциями, которые удалосьвычислить.В дальнейшем используются следующие известные в теории ДНФ понятия и факты. Множество всех наборов (α1 , .

. . , αn )таких, что αi ∈ {0, 1}, i = 1, . . . , n, называется n-мерным единичным кубом и обозначается через B n . Положим Nf ={α̃ ∈ B n : f (α̃) = 1}. Гранью куба B n называется множество g, для которого существует конъюнкция K, зависящая(не обязательно существенно) от переменных x1 , . . . , xn , такая, что g = NK .

Размерностью грани g называется числоlog2 |g|. Грань размерности 1 называется ребром. Грань называется интервалом функции f , если g ⊆ Nf , и максимальныминтервалом функции f , если g не содержится ни в каком другом ее интервале. Конъюнкции, соответствующие интервалам(максимальным интервалам) функции f называются импликантами (соответственно, простыми импликантами функции f ).Дизъюнкция всех простых импликант функции f называется ее сокращенной ДНФ и обозначается через Dfсокр . Говорят, чтовершина α̃ ∈ B n покрывается конъюнкцией K, если α̃ ∈ NK . Конъюнкция K поглощается функцией f (поглощаетсяДНФ D), если NK ⊆ Nf (соответственно, если NK ⊆ ND ). Через D \ K обозначим ДНФ, полученную из D отбрасываниемслагаемого K.

Другие используемые, но неопределяемые здесь понятия можно найти в [2] или [3]. В частности, здесьиспользуется следующаяЛемма 3.1 Пусть f — произвольная булева функция. Тогда1. ДНФ Dfсокр реализует функцию f .2. Всякая тупиковая, а значит, и всякая минимальная ДНФ функции f может быть получена из Dfсокр путемотбрасывания некоторых слагаемых.О вхождении конъюнкции в тупиковые ДНФОпределение 3.2 Конъюнкция K ∈ Dfсокр называется ядровой, если существует α̃ ∈ NK такая, что L(α̃) = 0 для любойконъюнкции L ∈ Dfсокр \ K. Множество всех ядровых конъюнкций функции f называется ее ядром.Теорема 3.1 (W.V.Quine) Конъюнкция K ∈ Dfсокр содержится во всех тупиковых ДНФ функции f тогда и только тогда,когда она входит в ядро этой функции.Доказательство.Необходимость.