В.Б. Алексеев - Введение в теорию сложности алгоритмов, страница 6

Напомним, что ,(Е Те в=э 1(О,...,О) =О, ( 6 Т2 л — ' 1(1,...,1) =1, ? Е Я С=; ДХЬ..., ХХв) = ((Х2 .. ° Хп), ,( Е Ь «=ь ~(хь..., х„) = св Ю с2х2 9... 9 с„х„, ( е М с=э для всех й = (оь..., оп) и Д = фы... „6„) таких, что 22(а; < Д), выполняется Д52) < ((В). Утверждение 3.1. При ввьтпорном предстпавлении функций длл распознавания свойства 'Яхь..., х„) Е Тв?" существует алгоритм (СФЭ) со сложностью 1. В этом случае выход х задается формулой х = ав.

Утверждение 3.2. При векторном представлении функций для распознавания свойства "у(хь..., х„) Е Т.?" сущесгпвует алгоритм (СФЭ~ со сложностью О. 25 В этом случае выход г задается формулой г = аг Утверждеюге 3.3. При ведгпорном представлении функций для Распознаваниэ свойства "1(хь...,хд) Щ 5? д срществрегп алгоРитм (СФЭ) со сложностью 0(>'>'), где А = 2" — длина входа. Доказательство. По определевию самодвойствеивых функций г(хг,...,х„) б Я тогда и только тогда, когда для 1побого сг (аъ, ° ., сг ) выполикетсЯ ((сгь ° ., >2») Р )(с22>..., сгд), то есть когда для всех 2 = О, 1,..., 2" ( — 1 выполняется ен ф. аг > о Таким образом, для расцозиаваиия свойства "( Е Я?д достаточно использовать 2» ~ бУлевьпс опеРаций а; Щ аг г г и затем взэть конъюнкцию полУченных зиачеввй. Общее число битовых операций будет 2" '+ 2" г — 1 = А> — 1.

'Утверждение 3.4. При векторном представлении функций для распознавания свойства "1(хь..., х„) б Ь?" сугцествует алгоритм (СФЭ) со сложностью 0(Ф), где Ж = 2» — длина входа. Л емма 3.3. ,((О,хг,...,х„) б Ь, .((1>хг>. ° тд) — = ((0>хг,. хд) Ща>д к (0,1). ПОКаэатЕЛЬСтВО. ЕСЛИ гс(Хд,..., Хд) = С>Х> ЩгаХгЩ...ЩС»Х»+СО, то, очевидца, 2(О,хг,...,хд) б Х и г"(1,хг> ° хд) дэ г(0 хг,...,хд) Щ сг. Для доказательства обратного перехода заметим, что для любой булевой функции справедливо представление ,> (хг> ° ° °, хд) Йг ' > (0> хг>..., хд) Щ х» " (1> хг,..., Хд)— = (хг Щ 1) ° ((О,хг,...,*д) Щ хг.

~(1,хг,...,хд) = х1 ' (ПО> х2> хд) Щ У(1> х2 ° ° > э»)) Щ г (0>х2 ° ° х») ° ПоэгдгмУ> если >Г(1 > хг» хд) ((О хг ° хд) Щ д то сегь г'(О,хг,...,хд) Щ,((1,хг„... >хд) ив э д, и ((О,хг,...,хд) б Ь, то и .((хг хг,,хд) б 1. Лемма доказана.

Будем строить алгоритм (СчгЭ) для распознавания свойства .,((хь ° ° хд) й Ь?д рекурсивио в соответствии с леммой. для проверки условия ((1, хъ ., хд) ээ г'(О, хг,..., хд) достаточно 2" — 1 бииариыхбитовыхопераций(2» 'сравиеиийа, = а;+2»- и2» ~ — 1ховьювкций полученных значений). Аналогично 2» — 1 биварвых операций дпстаточио для проверки условия у (1, *г,, хд) = ((О, хг,..., хд) Щ 1. для проверки условия ? (1, хг,..., хд) = г(0, хг,..., хд) щ и достаточво взять дизъюикцию двух получеивых результатов сраввевий. При этом общее число битовых операшщ 2(2» — 1) + 1 ( 2»+г.

Пусть Ь(и) — минимальное число битовых операций дпя ответа иа вопрос "1 (х11..., хп) б ь?" Тогда Ц1) = 1 (т.к. выход г н 1) и в соответствии с леммой Цтт) < Цтт Ц+ 2п+1 < Ци 2) + 2п+ 2п+1 < < Ь(и 3) + 2п-1 + 2п + 2п+1 « < Ц1)+2»+2»+... +2"+' <2п+з =4У. Утверждение 3.4 доказано. Утверждение 3.5. При вектпорном предстпавлении функций для распознавания свойстпва ",т(х1,..., х„) Е М?" сутцестпвуетп а мариам (СФЭ) со слохсностпью 0(тт'1он тт'), где 1т' = 2" — длина входа.

Локазатпельстпво. Известно, что ((х1,..., х„) б М тогда и только тогда, когда для любых двух наборов а и П таких, что а (а1,...,а; 1,0,ат+1,,а„) в (1 = (а1,...,ат 1,1,а;+1,...,ст„) (где т' — любое), выполняется Да) < (((т) [18]. Число указанных пар наборов (а, д) равно п 2" '. Таким образом, дпя распознавания свойства "( б М?ь дОСтатОЧНО ИСПОЛЬЗОВатъ И 2" 1 бИтОВЫХ цвранвй пХ < уп (то есть х -т у) и затем взять конъюнкцию полученных значений.

Общее число битовыхопеРацийбУдет п 2" 1+и 2" 1 — 1 = 1т 1обз 1'т'-1. Из утверждений 3. 1-3.5 и теоремы Поста о полноте [18] получаем спедутощее утверждение. Теорема 3.4. При вентпорном предстпавлении функций для распознавнив полнотпы систпемы функций сутцестпвуетп алгоритпм (СФЭ) со сложностпью 0(Л 1о8 Ат), где Л вЂ” длина входа. Замечание. Вороненка А. А. [6] нашел более быстрый алгоритм со сложностью 0(Ат1/)о8)71о81об Ат) дпя распознавания свойства монотонности (кдасс М), откуда следует, что в доспедней теореме оценку 0(Ат!о8 Ат) можно понизить до 0(1т'1т%д тт' 1об 1об Ат). 3.4. Распознавание сохранении двухместных предикатов Пусть Е» = (О, 1,..., к — 1) и пусть Е» — множество всех наборов дняны и с элементами из Е».

Через Р» будем обозначать множество всех й-звачных функпвй, то есть функций, отображаюппсс Е» в Е» при всех п. Определение. Предакатпом (тп-местным) на конечном множестве 0 называется любая функция В(у1... у ): 0 — + (истина, пожь1. Определение, Пусть ((х1... х„) б Р» и П(у»,уз) — 2-местный предикат на множестве Е». Будем говорить, что у(х1...

х„) сохраняетп преднватп В, если для любых наборов а = (а1...ст„) и )3 = (А т"и) вьшолнявгся вмпликгл;ия; (ЧрВ(а,, (3»)) -+ ВЦ(а), Щ)). Обозначим У(В) — класс всех фунхций,сохраняющих предикат В. Пусть а = (тзь..., а„), д = (Д,..., В„) — наборы с элементами из Р и  — 2-местный предихат на Р. Тогда определим предикат В" на Р" следующим образом: В" (а, ~3) = ~9В(а,,)?,), Если 7 = (ам...,а„»), б = (бп...,Бп»), то легхо видеть, что В"(а,Д) = В" '(т,6)МВ(а„,13„).

Задача. Фиксируем Е». Задан предихат В(ум уз) на Е». Требуется построить алгоритм для ответа на вопрос "Дх1... х„) Е У(В)?". При этом считается, что наборы из .Е» упорядочиваются лексикографически и функция у задается вектором т = (ав, аь..., а». т) ее значений на этих наборах; Х = й" — длина входа. В качестве алгоритмов будем рассматривать схемы из функциональных элементов с произвольными бинарными операциями над элементами множества Е», но будем говорить о битовой сложности, поскольку, если элементы множества Е» закодвровать двоичными словами, то хвжцую такую операцию можно смсделировать некоторым числом двоичных операпий, поэтому переход х двоичным схемам увеличивает сложность только в константу рэз, а мы рассматриваем сложность только по порядку.

Тривиальный алгоритм для этой задачи имеет сложность 0(Ф ) (проверха пар). Ясли предикат В истинен на д парах, то существует алгоритм со сложностью О(о") = 0(Ф"в'"). Однако верен следующей более сильный результат, который основав на методе перехода от задачи распознавания к задаче вычисления некоторого алгебраического выражения (1]. Теорема 3.5. Яля любого прединатпа В(уп уз) на Е» су~цвствуетп алгорипьн (СФЭ), распознаюи»ий "Дх»...хп) б У(В)?" со сложностью 0(И)ояг?), где М = 1с" — длина входа. Доказав»ел»став о. Пх»...х.) Ф У(В) е=ь Ба д(Вв(6 Р)г ВУ(а) П,3))) С=: Лбт, ДЗс, д(В'"(ст, )3)вс(Да) = с)8сЦ(Я = д) йВ(с, Н)) в=» Ч ВВ"(а )?)8 У(а) =с)итД = д)дгВ(с,д)) = асеев а,д '1/ 1/ (Я" (а, ЯЩ(а) = с)Щ(Р) = Ы)).

а,д:д(чд (ад В последнем выражении в первой дизъюнкции константное чиспо слагаемых, поэтому сложность вычисления этого выражения по порядку определяется сложностью вычисления второй дизъюнкпии. При фиксированных с, д вычисление логических переменных ов = (Да) = с) и е,1 ы (Щ) = Н) требует 0(Ф) операций. Пусть Е(Ф) = Ь'(п) — минимальная битовая сложность вычисления выражения 1/ад В"(а, Д)иее- при заданных иа, ез. Локаэкем, что Х(У) = 0(Л 1оя У) . Пусть а = ( ~, а„),Д = (Б,ф„), Тогда ~/В"(а„б)идей = 1/ Я" '(7,Б)В(а„,13„)и<«- „~оа з ~ —— а,д а=(«д„),ф=(1~3 ) = 1/ ~/ )1 (7 б) ~(аэ 1п)«Л,в )~>(зд„) «Ф ~" д" = '1/й" '(У 8) 1/ В(а~ Р )и<;р.>и~зд ~ = «й а д„ = ~/В" (7~Б) ~/пдд„) ~/ сайд„1 = «й а д:ягьд ) — Ц('1,/В" 1(7,6)и(«д 1ю(1 )), а «1 где юд, „1 =Чд„:дЬ М "ММ.) Отсюда Х/(и) < йЬ'(п — 1)+й"(й — 1)+Й-1, поскольку задача дпя п сводится к Й таким же задачам для н — 1, при этом дпя вычисления каждой вз 1са переменных ю требуется не более й — 1 дизъюнкций и после решения всех й подзадач требуется к — 1 дизъюнкций дпя вычисления дизъювкции по а„.

Переходя к Ь(Ф), получаем Ь(Ф) < ЙХф + 0(Ф), откуда, по теореме 2.4 о рекуррентном неравенстве, ЦФ) = 0(Ф1ояй). Теорема доказана. 3.5. Классы Г Пусть теперь гс(рц..., у ) — т-местный предикат на множестве Еь = (О, 1,..., я — 1). Если а; = (ац а«з,..., а„'), « = 1, 2,..., т— наборы с элементами нз Еы то определим Я"(амаь...,а,„) = ЧЖ(а,',а„...,а, ). Определение.

Будем говорить, что функция Дхь..., х„) из Рь сохраняет Я, если дпя любых т наборов йь йь, .., йт выпопняется виндикация ?? (йь й2, ° ., йт) ааг?Щ(й1)~,~(йэ)1...,,((йи)). (3.1) Рассмотрим следующий предикат г1 на Ез = (О, 11: и стина к=~ Зэ'(у; = О), Е(уь у)= ложь «=ю у = (1,...,1). Класс всех функций алгебры логики, сохраняющих предикат В обозначим Г . Классы г при т = 2,3,4,... образуют одну из 8 бесконечных цепочек замкнутых классов в алгебре логики. Рассмотрим следующую задачу.

Задача. Пусть т ) 2 — фиксированное натуральное число. Требуется построить алгоритм дпя ответа на вопрос "Дхь..., х„) б Е ?" при условии, что фушсция поступает на вход в виде вектора значений 1(хь, х„) = (ао, оь..., оэ з) длины?У = 2". Заметим, что трввиапьный алгоритм, основанный на просмотре всех выборок по т значений функции и проверке импликзлии (3.1) требует по порядку не менее?У операций.