Темпы роста произвольных конечных структур тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Комков Степан Алексеевич

• Комков Степан Алексеевич
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Комков Степан Алексеевич

Введение

Глава 1. Базовые понятия и утверждения

1.1 Основные определения и обозначения

1.2 Опорные утверждения

Глава 2. Темпы роста классов решётки Поста

2.1 Опорные утверждения и определения

2.2 Классы центральной части решётки Поста

2.3 Нетривиальные классы линейных функций

2.4 Классы счётных цепочек решётки Поста

2.5 Нетривиальные классы самодвойственных функций

2.6 Выводы

Глава 3. Классы с минимальным логарифмическим темпом

роста

3.1 Опорные утверждения и определения

3.2 Вспомогательные утверждения

3.3 Критерии минимального логарифмического темпа роста

3.4 Решётка клонов с минимальным логарифмическим темпом роста

Глава 4. Классы с логарифмическим темпом роста

4.1 Вспомогательные утверждения

4.2 Признак логарифмического темпа роста

Глава 5. Классы с экспоненциальным темпом роста

5.1 Вводная часть

5.2 Новые по порядку экспоненциальные темпы роста

Заключение

Список рисунков

Введение диссертации (часть автореферата) на тему «Темпы роста произвольных конечных структур»

Введение

Диссертационная работа посвящена исследованию темпов роста произвольных конечных структур. В ходе выполнения работы найдены значения темпов роста всех двухэлементных структур, получен ряд утверждений о нетривиальных конечных структурах с минимальным возможным темпом роста, найден порядок темпов роста конечных структур со слабо ограниченным множеством операций и определены новые конечные структуры с экспоненциальным темпом роста.

Под структурой в диссертационной работе подразумевается множество элементов с заданным на нём множеством операций, где каждая операция ставит один элемент множества в соответствие фиксированному для этой операции числу элементов множества.

Рассмотрим декартову степень Ап, п € N конечного множества А с заданным на нём множеством операций М. Элементы Ап будем называть наборами. Применяя операции изМк уже имеющимся наборам покоординатно, мы можем получать новые наборы:

Мы также можем получать новые наборы с помощью уже полученных наборов.

Множество наборов, из которого можно итеративно получить всё Ап7 называют генерирующим множеством для Ап по операциям из М.

Темпом роста пары (А,М) называют функцию (1(а,м) (п), п € N. Для каждого п функция d(A,м) (п) равна числу наборов в минимальном генерирующем множестве для Ап по операциям из М. Таким образом, асимптотика темпа роста характеризует исчислимость заданного множества операций. Функцию л(а,м) (п) также обозначают через (1р(п), где ^ = (А,М).

Пример 1. Пусть А = {0,1} М = {-}. Тогда, d(A,м)(n) = 2П-1.

Пример 2. Пусть А = {0,1,2} М = {+то<1 з}- Тогда )(п) = п.

Актуальность изучения темпов роста произвольных конечных структур для практических задач была показана Хьюби Ченом [24] на основе подкван-торной задачи удовлетворения ограничений (QCSP) и задачи удовлетворения ограничений (CSP).

Задача CSP заключается в проверке истинности формулы

3xi... Зхп (Ri{xii,... ) Л ... Л Rpix.p,... ,хгрр.

Здесь Ri, 1 ^ i ^ р — это предикаты, заданные на некотором конечном множестве А. Известно, что CSP является NP-полной задачей.

Несмотря на NP-сложность, существует большое количество методов и эвристик для решения задач CSP [53]. Это обусловлено тем, что на практике возникает множество задач удовлетворения ограничений.

Так, практическим примером задачи CSP является задача автоматического вывода типа данных компилятором [34; 54]. Вывод типов характерен для функциональных языков программирования, хотя со временем он был частично реализован и в объектно-ориентированных языках.

Другим практическим примером задачи удовлетворения ограничений является задача распределения регистров [22] — размещение наиболее часто используемых переменных компилируемой программы в быстродействующих регистрах процессора. При этом две переменные не могут занимать один и тот же регистр одновременно.

Задача Ш-QCSP является обобщением CSP следующего вида:

Ух!... Ухт (Зхт+1... Зхп (в,! (xq,... ) Л ... Л Rp(x1pi ,... ,хгрр. (1)

Известно, что Ш-QCSP является уже PSPACE-полной задачей [23].

На практике необходимость решать задачу Ш-QCSP возникает, например, на производстве, когда необходимо гарантировать реализуемость продукта для всех возможных определённых заказчиком опций. Дополнительным примером возникновения задачи Ш-QCSP на практике является задача планирования в условиях неопределённости, когда необходимо проверить осуществимость действия независимо от возможных событий [48].

Для решения задач подкванторного удовлетворения ограничений существует множество подходов [29; 50]. Часто они заключаются в некотором обобщении подходов к решению задачи CSP [27].

Однако при определённых ограничениях можно напрямую свести задачу Ш-QCSP к задаче CSP. Допустим, что среди предикатов формулы (1) могут встречаться не любые предикаты, а только предикаты из некоторого подмножества всех предикатов. С помощью соответствия Галуа [18; 19] этому подмножеству предикатов можно сопоставить замкнутое множество операций М па множестве А. В работе Хьюби Чена показано, что если темп роста пары (А,М) ограничен сверху полиномом и существует полиномиальный алгоритм построения генерирующего множества для Ап по операциям из М, то в этом случае задача II2-Q0SP сводится к задаче CSP за полиномиальное время.

Приведённый результат доказывает важность изучения темпов роста произвольных конечных структур.

Первым изучение темпов роста начал Джеймс Уиголд. Он опубликовал цикл работ, в котором подробно исследованы возможные темпы роста конечных групп. Далее приведены два наиболее известных результата, связывающих темп роста группы с её алгебраическими свойствами.

Теорема (Темп роста конечной несовершенной группы). Пусть F — конечная несовершенная, группа, F' — коммутанта группы, F, а = dp(1), ß = dp/p'(1).

1. Пусть s — порядок наименьшего простого неабелевого гомоморфного образа, группы, F (если такой существует) ип ^ (а + 1 + logsn)/ß. Тогда, dp(п) = п.

2. Пусть все простые гомоморфные образы группы, F являются абелевы-ми ип ^ а/ß. Тогда, dp(п) = ß • п.

Теорема (Темп роста нетривиальной конечной совершенной группы). Пусть р _ нетривиальная конечная, совершен нал группа, а = dp (1), а s — порядок наименьшего простого неабелевого гомоморфного образа, группы, F. Тогда, log|_p| п ^ dp (п) < а + 1 + logs п для всех п ^ 1.

Более грубые формулировки приведённых теорем были получены уже в первой работе цикла [55]. Однако в дальнейшем их удалось уточнить [56; 57].

Последующие работы цикла посвящены более точной оценке темпов роста некоторых классов конечных совершенных групп [41; 58].

Позже Джеймс Уиголд изучил возможные темпы роста конечных полугрупп. В [59] он доказал следующие две теоремы, описывающие темп роста конечной полугруппы в зависимости наличия или отсутствия в ней единичного элемента.

Теорема (Темп роста конечной полугруппы с единичным элементом). Пусть р _ конечная полугруппа с единичным элементом, Р' — группа обратимых элементов группы Г, т минимальное числе элементов, из которых можно получить всё ^ той Р'. Тогда, ^(п) = ^'(п) + т • п.

Теорема (Темп роста конечной полугруппы без единичного элемента). Пусть р _ коне чная полугруппа без единичного элемента. Тог да для всех п ^ 2

В [59] также доказано, что если в конечной полугруппе есть элементы, непредставимые как произведение двух элементов, то темп роста этой полугруппы ограничен снизу функцией 2П — 1. В [45] для конечных полугрупп без единичного элемента доказано, что если каждый элемент полугруппы представляется как произведение двух элементов, то темп роста ограничен снизу функцией 2П. Тем самым доказано следующее далее утверждение.

Теорема (Нижняя оценка темпа роста конечной полугруппы без единичного элемента). Пусть Р — конечная, полугруппа без единичного элемента. Тогда,

В [47] изучены темпы роста других классических конечных алгебраических структур: колец, модулей, алгебр и алгебр Ли. Оказалось, что темпы роста приведённых структур в нетривиальных случаях являются либо логарифмическими, либо линейными. Темпы роста линейны для несовершенных алгебр Ли, всех модулей, а также для колец и алгебр, в которых существует элемент непредставимый как произведение двух элементов. В остальных случаях темп роста логарифмический.

Несмотря на большое количество работ, посвящённых исследованию темпов роста конечных структур, до 2013-го года не были известны конечные структуры, для которых темп роста не был бы константным, логарифмическим, линейным или экспоненциальным. Начиная с 2013-го года Кис Кирн, Эмуэль Киш и Агнэш Сэндрэй публикуют цикл работ, где, в частности, показывают, что для любого т € N найдётся конечное множество с заданным на нём множеством операций с темпом роста порядка пт [36].

В остальных работах цикла [37; 38] авторы обобщают критерии логарифмического, линейного и экспоненциального темпа роста на более широкие классы конечных алгебраических структур.

выполняется

(1¥ (п) ^ 2п — 1.

Позже Дмитрий Николаевич Жук доказал следующую теорему об отсутствии темпов роста строго асимптотически зажатых между любым полиномом и любой экспоненциальной функцией.

Теорема ([62].). Пусть Р — конечная структура. Тогда, верно ровно одно из утверждений:

1. Существуют такие С > 0, Ь > 1, что ¿р(п) ^ С • Ъп;

2. Существует такой многочлен р(х) от одной переменной, что (1р (п) ^ р(п).

Известно, что темп роста структуры (А,М), где |А| = к > 1, не может быть меньше чем \ogfr п.

Всё ещё открыт вопрос о существовании конечной структуры, для которой темп роста превосходит любую логарифмическую функцию, но не превосходит линейной функции.

Для темпа роста <Лр (п) можно определить двойственную функцию кр(т) = п € N | ¿р(п) ^ т}, для которой выполняется

(1р(п) ^ т ^ кр(т) ^ п.

Приведённая функция не только полезна при изучении темпов роста, но и представляет самостоятельный интерес. Существует цикл работ, посвящённых этой функции, начинающийся с [26].

Стоит отметить, что также изучают темпы роста бесконечных структур. Известны результаты для конечно порождённых групп [25; 40; 52; 55; 60], для других конечно порождённых алгебраических структур |36 38: 47], для решётчато упорядоченных групп [30], для бесконечных полугрупп [44]. Принципиальное отличие темпов роста бесконечных структур заключается в том, что темп роста бесконечной структуры может равняться бесконечности или быть ограничен константной даже в нетривиальном случае.

Пример 3. ^(М;{+})(1) = 1, й(М{+})(п) = ж, п ^ 2.

Пример 4 ([47]). Пусть Р — бесконечная конечно порождённая простая группа. Тогда, (1р(п) ^ С, п € N для некоторого С.

Для изучения темпов роста в настоящей диссертационной работе применён аппарат, выходящий за рамки алгебраических методов: конечное множество

с заданным на нём множеством операций рассматривается как^-значная логика и некоторое множество операций ^-зпачпой логики. Например, конечную группу Е порядка к можно без утери общности рассматривать как пару (Ек,{°}), где ° — бинарная операция.

Доказано, что при замене множества операций М па его замыкание по операциям суперпозиции [М] ([39]) темп роста полученной пары (Ек,[М]) равен темпу роста пары (Ек,М).

Приведённый факт позволяет использовать результат Эмиля Леона Поста, построившего решётку всех замкнутых по операциям суперпозиции классов функций булевой логики [46]. Этот результат, известный как решётка Поста, позволяет определить темпы роста всех возможных двухэлементных структур.

Известно, что для предикатов с заданной конечной областью определения существует такой алгебраический оператор замыкания, что порождённая им решётка замкнутых множеств предикатов антиизоморфна решётке клонов с такой же областью определения [18; 19]. Клонами называют замкнутые классы функций, содержащие все селекторы. Этот антиизоморфизм называется соответствием Галуа. Он применяется, например, для изучения структуры решётки замкнутых классов функций [13; 61].

В диссертационной работе соответствие Галуа неоднократно используется для доказательства и формулировки результатов. С его помощью получен критерий минимального логарифмического темпа роста в терминах предикатов, а также описаны темпы роста конечных структур, множество операций которых сохраняет лишь конечное число важных существенных предикатов.

Критерий минимального логарифмического темпа роста в терминах предикатов позволяет получить критерий минимального логарифмического темпа роста в терминах функций. Также критерий минимального логарифмического темпа роста в терминах предикатов позволяет доказать, что решётка замкнутых классов функций с минимальным логарифмическим темпом роста не отличается по мощности от полной решётки классов функций многозначной логики ни в "дЛИНу" 5 ни в "ШИрИНу" [21]. Здесь минимальным логарифмическим темпом роста называется такой темп роста )(п), что (1^м)(п) — п = 0(1)-* то есть темп роста, отличающийся от минимального возможного не более чем на предопределённую константу.

Полученные утверждения для решётки замкнутых классов функций с минимальным логарифмическим темпом роста позволяют попять устройство

решётки замкнутых классов функций многозначной логики. Как следствие доказанных в настоящей работе теорем получено, что в предполных классах сохранения подмножества континуально много в "длину" и в "ширину" таких замкнутых классов функций, что они не принадлежат никакому другому пред-полному классу.

Для произвольной конечной структуры доказано, что если все её операции сохраняют лишь конечное число важных существенных предикатов, то темп роста данной структуры ограничен сверху некоторой логарифмической функцией. То есть, если мы "слабо" ограничим множество возможных операций конечной структуры, это не выведет её из класса структур с логарифмическим темпом роста.

Наконец, во всех вышеприведённых классических результатах экспоненциальный темп роста определяется как темп роста из класса 2в(п) при п ^ ж. В настоящей работе исследуются классы экспоненциальных темпов роста, на которые разбиваются темпы роста из класса

2в(п)

п ^ ж, при выносе

асимптотического ограничения из показателя. Оказывается, что разнообразие возможных порядков экспоненциальных темпов роста превосходит известное разнообразие не более чем полиномиальных темпов роста даже с точностью до основания экспоненты.

Целью работы является исследование темпов роста произвольных конечных структур. Так как для булевой алгебры известна полная решётка замкнутых классов функций, то для двухэлементных структур задача состоит в нахождении точных значений всех возможных темпов роста. Для произвольных конечных структур задача заключается в исследовании крайних случаев: наиболее быстро- и медленно-растущих темпов роста.

Известно, что задача II2-Q0SP может быть сведена к задаче CSP в зависимости от функционального множества, задающего язык ограничений. Тем самым представляют интерес утверждения о темпах роста, сформулированные в терминах предикатов, сохраняемых заданными операциями. Это позволяет напрямую исследовать язык ограничений, не переходя к функциональному множеству, задающему его.

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Получить точные значения темпов роста всех возможных двухэлементных структур;

2. Оценить мощность решётки конечных структур фиксированного размера с минимальным логарифмическим темпом роста;

3. Получить критерий минимального логарифмического темпа роста;

4. Исследовать темпы роста конечных структур лишь с конечным числом существенных ограничений на их множество операций;

5. Исследовать возможные порядки экспоненциального темпа роста конечных структур.

Научная новизна:

1. Впервые получены точные значения темпов роста классов функций из решётки Поста;

2. Впервые обособлены и изучены конечные структуры с минимальным логарифмическим темпом роста: получены различные формулировки критерия минимального логарифмического темпа роста, а также получена мощность решётки замкнутых классов функций с минимальным логарифмическим темпом роста в глубину и в ширину;

3. Впервые получены темпы роста произвольных конечных структур лишь с конечным числом существенных ограничений на их множество операций;

4. Впервые получены темпы роста с асимптотическим ограничением не в показателе экспоненты.

Результаты исследований являются подлинными и оригинальными и, кроме специально оговорённых случаев, получены лично автором.

Теоретическая и практическая значимость Практическая применимость была описана ранее: в некоторых случаях задачу Ш-QCSP можно свести к более простой задаче CSP в зависимости от порядка темпа роста и возможности построения генерирующего множества для некоторой внутренней структуры задачи.

Введённые в работе утверждения и понятия могут быть использованы в дальнейшем при изучении теоретических вопросов алгоритмической сложности и экстремальной комбинаторики.

Методология и методы исследования. В работе применялись методы дискретной математики, алгебры, комбинаторики и теории вероятностей. В частности, доказательства полученных в работе утверждений опираются на следующие известные результаты: соответствие Галуа, определяющее антиизоморфизм между решёткой клонов и решёткой замкнутых классов предикатов;

и

решётка Поста, определяющая решётку всех замкнутых по операциям суперпозиции классов функций булевой логики; теорема Анселя, определяющая разбиение булева куба на цепи, обладающие определёнными свойствами; теорема Катоны, определяющая минимальный размер тени множества строк с одного уровня булева куба; теорема Шпернера, определяющая максимальное число попарно несравнимых булевых строк одного размера; теоремы Милне-ра, Франкла-Гронау и Гронау, определяющие максимальное число попарно несравнимых булевых строк одного размера с некоторыми ограничениями на их объединения; теорема Розенберга, определяющая все предполные классы ^-значной логики; неравенство Чернова, оценивающее вероятность отклонения биномиального распределения от своего математического ожидания на определённую величину с ростом числа испытаний.

Основные положения, выносимые на защиту: На защиту выносятся обоснование актуальности решаемых задач, методология, принятая для исследования, научная новизна, теоретическая и практическая значимость работы, а также следующие положения, которые подтверждаются результатами исследований, представленными в Заключении диссертации:

1. Значения темпов роста всех клонов решётки Поста и их связь с классическими задачами экстремальной комбинаторики;

2. Критерии минимального логарифмического темпа роста в терминах предикатов и в терминах функций;

3. Оценки мощности решётки клонов с минимальным логарифмическим темпом роста в глубину и в ширину;

4. Порядок темпов роста клонов, сохраняющих лишь конечное число важных существенных предикатов;

5. Новые ранее неописанные классы экспоненциальных темпов роста, чье разнообразие, как оказалось, превосходит разнообразие не более чем полиномиальных темпов роста.

Достоверность полученных результатов обеспечивается приведёнными строгими математическими доказательствами.

Результаты работы проходили апробацию на научных конференциях и семинарах и опубликованы в рецензируемых научных журналах.

Результаты других авторов, упомянутые в тексте диссертации, отмечены соответствующими ссылками.

Апробация работы. Основные результаты работы докладывались на следующих международных и всероссийских конференциях и на следующих семинарах:

— Международные научные конференции студентов, аспирантов и молодых ученых "Ломопосов-2019" (с 8 по 12 апреля 2019 года) и "Ломоносов-2021" (с 12 по 23 апреля 2021 года), секция "Математика и механика", Москва, МГУ;

— XII Международная научная конференция "Интеллектуальные системы и компьютерные науки", приуроченная к 85-летию со дня рождения профессора Московского университета В. Б. Кудрявцева, с 29 ноября по 3 декабря 2021 года, Москва, МГУ;

— Ежегодные научные конференции "Ломоносовские чтения-2018" (с 16 по 27 апреля 2018 года), "Ломоносовские чтения-2019" (с 15 по 25 апреля 2019 года), "Ломоносовские чтения-2020" (с 21 по 28 октября 2020 года) и "Ломоносовские чтения-2021" (с 21 по 28 апреля 2021 года), секция "Математика", Москва, МГУ;

— Научный семинар "Теория автоматов" под руководством профессора Кудрявцева Валерия Борисовича, механико-математический факультет МГУ имени М.В.Ломоносова, 2018, 2019 и 2021 года;

— Научный семинар "Нейронные сети" под руководством доцента Ча-совских Анатолия Александрович, научного сотрудника Половникова Владимира Сергеевича, старшего научного сотрудника Говорко Алексея Александровича, механико-математический факультет МГУ имени М.В.Ломоносова, 2018, 2019, 2020 и 2021 года.

Личный вклад. Автором решены поставленные в работе задачи: найдены значения темпов роста произвольных двухэлементных структур, доказан критерий минимального логарифмического темпа роста, найдена мощность решётки конечных структур с минимальным логарифмическим темпом роста, найден порядок темпов роста конечных структур лишь с конечным числом существенных ограничений, найдены новые порядки экспоненциальных темпов роста. Полученные в рамках работы утверждения и следствия из них сформулированы и доказаны автором самостоятельно. Основные результаты оформлены и опубликованы в рецензируемых научных изданиях, рекомендованных для защиты. По результатам исследований подготовлены и сделаны доклады на научных конференциях и семинарах.

Публикации. Основные результаты по теме диссертации изложены в 8 научных изданиях |1 8|: 0 и периодических научных журналах, рекомендованных для защиты по специальности 01.01.09 [1; 2; 4; 5; 7; 8], из которых 4

— в периодических научных журналах, индексируемых Web of Science, Scopus и RSCI |1: 2: 4: 7|: 2 и тезисах докладов [3; 6]. Работ, написанных в соавторстве, нет.

Объем и структура работы. Диссертация состоит из Введения, 5 глав, Заключения. Полный объём диссертации составляет 111 страниц. Список литературы содержит 62 наименования.

Краткое содержание работы.

В главе 1 вводятся основные определения и обозначения, а также доказываются базовые утверждения, используемые на протяжении всей работы.

В разделе 1.1 определяются понятия набора и выводимости набора из других наборов. Определяется понятие генерирующего множества — такого множества наборов, что из него выводятся все возможные наборы. Через генерирующее множество определяется понятие минимального генерирующего множества. Определяется понятие собственных строк генерирующего множества и, наконец, темп роста определяется через введённые термины. Также в разделе вводятся необходимые определения для формулировки соответствия Галуа.

В разделе 1.2 вводятся базовые утверждения о темпе роста, определяющие основные характеристики этой функции.

В лемме 1 доказывается, что если расширить множество операций структуры, то значения её темпа роста от этого не увеличатся. Данное утверждение, несмотря на свою простоту, является полезным для нахождения темпов роста

— оно позволяет оценивать темп роста интересующей структуры через уже найденные темпы роста.

Лемма 1. Пусть А С В С Рк} к ^ 2. Тогда d(Ek,А){р) ^ d(Ek,в){р).

Из двух следующих далее замечаний следует, что для нахождения всех возможных темпов роста достаточно найти темпы роста только тех структур, у которых множество операций является клоном.

Замечание 1. d(Ek)(п) = d(EkuG)(n), к ^ 2, где G — множество всех селекторов.

Замечание 2. м)(п) = ,[щ(п), к ^ 2.

Следующее далее замечание определяет минимальный возможный темп роста для конечной структуры.

Замечание 3. <Л(Ек,м)(п) ^ \logb п\, к ^ 2.

Лемма 2 является критерием генерирующего множества. В диссертационной работе используется определение темпа роста через мощность минимального генерирующего множества. Тем самым приведённая лемма является одним из основных инструментов для изучения темпов роста.

Лемма 2. Пусть М — замкнутое по операциям суперпозиции множество функций к-значной логики, содержащее все селекторы. Множество X — генерирующее множество по операциям из М тогда и только тогда, когда из собственных строк генерирующего множества X, используя каждую собственную строку не более одного раза, нельзя составить такую матрицу, что все её столбцы принадлежат, какому-то нетождественному предикату р € 1пу(М).

В главе 2 найдены значения темпов роста всех возможных пар вида (Е2,М), где М С Р2. Согласно предыдущим замечаниям для этого достаточно найти темпы роста только тех пар, где М — клоп. В этой главе используется полная структура решётки клонов булевой логики, известная как решётка Поста.

В разделе 2.1 приведены необходимые определения и обозначения, а также классические результаты экстремальной комбинаторики, которые потребовались для определения темпов роста некоторых клонов: теорема Анселя о разбиении булева куба на цепи, теорема Катоны о размере тени множества булевых строк, теорема Шпернера о максимальном числе попарно несравнимых подмножеств конечного множества, а также теоремы Милнера, Франкла-Гронау и Гронау о максимальном числе попарно несравнимых подмножеств конечного множества с некоторыми ограничениями на их объединения.

В разделе 2.2 найдены значения темпов роста классов функций из центральной части решётки всех клонов алгебры логики. В данный раздел не входят только нетривиальные классы функций, содержащие линейные и самодвойственные функции.

В трёх следующих далее теоремах определяются значения темпов роста класса Р2 и классов функций, сохраняющих подмножества.

Теорема 1. 6,{е2,с{)(п) = |~1°ё2п]. Здесь С1 = Р2 = Ро1({ (0 1) }).

Теорема 2. ^е2,с2)(п) = ^,(е2,с3)(п) = (п + 1)]. Здесь С2 = Т\ =

Ро1({ (1) }) м Сз = Т0 = Ро1({ (0) }).

Теорема 3. ¿,{Е2}Сл)(п) = (п + 2)]. Здесь СА = Тх П Т0 ^ Ро1({ (1), (0) }).

В теореме 4 определяются значения темпов роста клонов, не содержащих функций с более чем одной существенной переменной.

Теорема 4. 1. й^о^п) = 2п.

Л(^Р5)(п) = й(^,о8)(п) = 2П - 1 5. й(Еъо6)(п) = 2п - 2.

4- (1(е2,04)(п) = 2П-1. 5. (1{Е2^)(П) = 2п-1 - 1.

Здесь Ох = [{ж}], 05 = [{х,1}], 08 = [{ж,0}], 06 = [{х,1,0}], Оа = [{х,х + 1}], Од =[{Х,Х + 1,0,1}].

Следующая далее теорема определяет значения темпов роста классов монотонных функций и монотонных функций, сохраняющих подмножества.

Теорема 5. = ^еъа2)(п) = е2,аз)(п) = ^м)(п) = ф(п) = 1о&2п +

2 • п + о(^2 п) при п ^ ж. Здесь А1 = М = Ро1({ (011 ) }), А2 =

М П Т1 = Ро 1({ (000 \) ,(1]}),Аз = М П Т0 = Ро 1({ (001\) ,(0)}), Л4 = М П Т1 П Т» = Ро 1({ (011) ,(1),(0)}).

Значения темпов роста классов функций, являющихся замыканием конъюнкции или дизъюнкции с константными функциями, определяются в двух следующих далее теоремах.

Список литературы диссертационного исследования кандидат наук Комков Степан Алексеевич, 2022 год

Список литературы

9. Ансель, Ж. О числе монотонных булевых функций п переменных / Ж. Ан-сель // Кибернетический сборник. Новая серия. — 1968. — № 5. — С. 53—63.

10. Бабищ Д. Н. Решение проблемы классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты / Д. Н. Бабин // Вестник Нижегородского университета им. НИ Лобачевского. Серия: Математическое моделирование и оптимальное управление. — 2000. — № 1. — С. 23-26.

11. Быковская, С. В. Полные системы одноместных предикатов для классов Поста / С. В. Быковская // Вестник Московского университета. Серия 1. Математика. Механика. — 2016. — № 4. — С. 33—38.

12. Быстрыгова, А. В. Параметро-эффективная расшифровка булевых функций из замкнутых классов Поста / А. В. Быстрыгова // Дискретная математика. — 2019. — Т. 31, № 2. — С. 34—56. — Discrete Math. Appl., 30:5 (2020), 285-301.

13. Жук, Д. Н. Предикатный метод построения решетки Поста / Д. Н. Жук // Дискретная математика. — 2011. — Т. 23, № 2. — С. 115 128. — Discrete Math. Appl., 21:3 (2011), 329-344.

14. Калаче в, Г. В. Об оценках мощности плоских схем для замкнутых классов булевых функций / Г. В. Калачев // Интеллектуальные системы. Теория и приложения. — 2016. — Т. 20, № 3. — С. 52—57.

15. Кибкало, М. А. Об автоматной сложности классов Поста булевых функций / М. А. Кибкало // Интеллектуальные системы. — 2011. — Т. 15, ..V« 1-4. - С. 379-400.

16. Лупанов, О. Б. Введение в математическую логику / О. Б. Лупанов ; под ред. А. Б. Угольников. — Изд-во ЦПИ при механико-математическом факультете МГУ имени М. В. Ломоносова, 2007. — 192 с.

17. Никольский, С. М. Курс математического анализа / С. М. Никольский. — М. : Наука, 1990. — 528 с. — Учебник для вузов, 4-е изд.

18. Теория Галуа для алгебр Поста I / В. Г. Бодиарчук [и др.] // Кибернетика. - 1969. Л" 3. С. 1-10.

19. Теория Галуа для алгебр Поста II / В. Г. Боднарчук [и др.] // Кибернетика. - 1969. - № 5. - С. 1-9.

20. Члепова, Т. С. О слоистости замкнутых классов булевых функций и функций k-значной логики / Т. С. Членова // Интеллектуальные системы. Теория и приложения. — 2014. — Т. 18, Л'° 1. С. 259—262.

21. Янов, Ю. И. О существовании k-значных замкнутых классов, не имеющих конечного базиса / Ю. И. Янов, А. А. Мучник // Докл. АН СССР. Т. 127. — 1959. - С. 44-46.

22. A dynamic distributed constraint satisfaction approach to resource allocation / P. J. Modi [et al] // International Conference on Principles and Practice of Constraint Programming. — Springer. 2001. — P. 685—700.

23. Chen, H. M. The computational complexity of quantified constraint satisfaction / H. M. Chen. — Cornell University, 2004. — 88 p.

24. Chen, H. Quantified constraint satisfaction and the polynomially generated powers property / H. Chen // International Colloquium on Automata, Languages, and Programming. — Springer. 2008. — P. 197—208.

25. Erfanian, A. A problem on growth sequences of groups / A. Erfanian // Journal of the Australian Mathematical Society. — 1995. — Vol. 59, no. 2. — P. 283—286.

26. Erfanian, A. A note on growth sequences of finite simple groups / A. Erfanian, J. Wiegold // Bulletin of the Australian Mathematical Society. — 1995. — Vol. 51, no. 3. — P. 495—499.

27. Ferguson, A. Quantified Constraint Satisfaction Problems: From Relaxations to Explanations / A. Ferguson, B. O'Sullivan // IJCAI. — 2007. — P. 74^79.

28. Frank/ P. On Sperner families satisfying an additional condition / P. Frankl // Journal of Combinatorial Theory, Series A. — 1976. — Vol. 20, no. 1. — P. 1—11.

29. Gent, I. P. QCSP-Solve: A solver for quantified constraint satisfaction problems / I. P. Gent, P. Nightingale, K. Stergiou // IJCAI. Vol. 5. — 2005. — P. 138—143.

30. Glass, A. Growth sequences — a counterexample / A. Glass, H.H. Riedel / / algebra universalis. — 1985. — Vol. 21, no. 2. — P. 143—145.

31. Gronau, H.-D. 0. On Sperner families in which no 3 sets have an empty intersection / H.-D. O. Gronau // Acta Cybernetica. — 1979. — Vol. 4, no. 2. — P. 213—220.

32. Gronau, H.-D. 0. On Sperner families in which no k sets have an empty intersection / H.-D. O. Gronau // Journal of Combinatorial Theory, Series A. — 1980. — Vol. 28, no. 1. — P. 54—63.

33. Gronau, H.-D. 0. On Sperner families in which no k sets have an empty intersection, II / H.-D. O. Gronau // Journal of Combinatorial Theory, Series A. _ 1981. — Vol. 30, no. 3. — P. 298—316.

34. Jim, T. Type inference in systems of recursive types with subtyping / T. Jim, J. Palsberg // Available on authors' web page. — 1999.

35. Katona, G. A theorem of finite sets / G. Katona // Theory of Graphs. — Springer. New York, London, 1968. — P. 187—207.

36. Kearnes, K. A. Growth rates of algebras, I: Pointed cube terms / K. A. Kearnes, E. W. Kiss, Ä. Szendrei // Journal of the Australian Mathematical Society. — 2016. — Vol. 101, no. 1. — P. 56 94.

37. Kearnes, K. A. Growth rates of algebras, II: Wiegold dichotomy / K. A. Kearnes, E. W. Kiss, Ä. Szendrei // International Journal of Algebra and Computation. — 2015. — Vol. 25, no. 04. — P. 555—566.

38. Kearnes, K. A. Growth rates of algebras, III: finite solvable algebras / K. A. Kearnes, E. W. Kiss, Ä. Szendrei // Algebra universalis. — 2016. — Vol. 76, no. 2. — P. 199—222.

39. Lau, D. Function Algebras on Finite Sets / D. Lau. — Berlin, Heidelberg : Springer Science & Business Media, 2006. — 668 p.

40. Lennox, J. C. Generators and killers for direct and free products / J. C. Lennox, J. Wiegold // Archiv der Mathematik. — 1980. — Vol. 34, no. 1. — P. 296—300.

41. Meier, D. Growth sequences of finite groups V / D. Meier, J. Wiegold // Journal of the Australian Mathematical Society. — 1981. — Vol. 31, no. 3. — P. 374—375.

42. Milner, E. C. A combinatorial theorem on systems of sets / E. C. Milner // Journal of the London Mathematical Society. — 1968. — Vol. 1, no. 1. — P. 204—206.

43. Mitzenmacher, M. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis / M. Mitzenmacher, E. Upfal. — Cambridge, United Kingdom : Cambridge university press, 2017. — 366 p.

44. On the growth of generating sets for direct powers of semigroups / J. T. Hyde [et al] // Semigroup Forum. Vol. 84. — Springer. 2012. — P. 116—130.

45. Polldk, G. Growth sequence of globally idemportent semigroups / G. Polläk // Journal of the Australian Mathematical Society. — 1990. — Vol. 48, no. 1. — P. 87—88.

46. Post, E. Two-valued iterative systems of mathematical logic / E. Post. — Princeton : Princeton University Press, 1941. — 122 p. — volume 5 of Annals of Mathematics studies.

47. Quick, M. Growth of generating sets for direct powers of classical algebraic structures / M. Quick, N. Ruskuc // Journal of the Australian Mathematical S0Ciety. — 2010. — Vol. 89, no. 1. — P. 105—126.

48. Rintanen, J. Constructing conditional plans by a theorem-prover / J. Rinta-nen // Journal of Artificial Intelligence Research. — 1999. — Vol. 10. — P. 323—352.

49. Rosenberg, I. Uber die funktionale Vollständigkeit in den mehrwertigen Logiken / I. Rosenberg // Pozpravy Ceskoslovensken Akad. Ved. — 1970. — Vol. 80, no. 3. — P. 3—93.

50. Solving quantified constraint satisfaction problems with value selection rules / J. Gao [et al.] // Frontiers of Computer Science. — 2020. — Vol. 14, no. 5. — P. 1—11.

51. Sperner, E. Ein satz über untermengen einer endlichen menge / E. Sperner // Mathematische Zeitschrift. — 1928. — Vol. 27, no. 1. — P. 544 548.

52. Stewart, A. Growth sequences of finitely generated groups II / A. Stewart, J. Wiegold // Bulletin of the Australian Mathematical Society. — 1989. — Vol. 40, no. 2. — P. 323—329.

53. Tsang, E. Foundations of constraint satisfaction: the classic text / E. Tsang. — Essex, UK : BoD-Books on Demand, 2014. — 444 p.

54. Type inference for static compilation of JavaScript / S. Chandra [et al.] // ACM SIGPLAN Notices. — 2016. — Vol. 51, no. 10. — P. 410 429.

55. Wiegold, J. Growth sequences of finite groups / J. Wiegold // Journal of the Australian Mathematical Society. — 1974. — Vol. 17, no. 2. — P. 133—141.

56. Wiegold, J. Growth sequences of finite groups II / J. Wiegold // Journal of the Australian Mathematical Society. — 1975. — Vol. 20, no. 2. — P. 225 229.

57. Wiegold, J. Growth sequences of finite groups III / J. Wiegold // Journal of the Australian Mathematical Society. — 1978. — Vol. 25, no. 2. — P. 142 144.

58. Wiegold, J. Growth sequences of finite groups IV / J. Wiegold // Journal of the Australian Mathematical Society. — 1980. — Vol. 29, no. 1. — P. 14—16.

59. Wiegold, J. Growth sequences of finite semigroups / J. Wiegold, H. Lausch // Journal of the Australian Mathematical Society. — 1987. — Vol. 43, no. 1. — P. 16—20.

60. Wiegold, J. Growth sequences of finitely generated groups / J. Wiegold, J. S. Wilson // Archiv der Mathematik. — 1978. — Vol. 30, no. 1. — P. 337 343.

61. Zhuk, D. The Lattice of All Clones of Self-Dual Functions in Three-Valued Logic. / D. Zhuk //J. Multiple Valued Log. Soft Comput. — 2015. — Vol. 24, no. 1—4. — P. 251—316.

62. Zhuk, D. The size of generating sets of powers / D. Zhuk // Journal of Combinatorial Theory, Series A. — 2019. — Vol. 167. — P. 91—103.

Список рисунков

2.1 Решётка клонов алгебры логики...................... 31

2.2 Разбиение решётки Поста на основе темпа роста............ 58

2.3 Разбиение решётки Поста на сильные и слабые классы Поста..... 59

2.4 Разбиение решётки Поста на основе порядка функции Шеннона автоматной сложности........................... 60

2.5 Разбиение решётки Поста на основе слоистости............. 61

2.6 Разбиение решётки Поста на основе порядка функции Шеннона потенциала функций класса........................ 62

2.7 Разбиение решётки Поста на основе порядка роста числа запросов, необходимых для расшифровки функций класса............ 63