ИСТИНА

Получение новых оценок сложностных характеристик булевых функций и графов

The aim of this project is to obtain new estimates of such characteristics of graphs and circuits as chromatic number of graphs with special restrictions, pseudopolynomial complexity of Boolean functions, dynamic activity of circuits, circuit complexity of Boolean functions, test complexity of Boolean functions.

1. Предполагается найти оценку хроматического числа 2-псевдокубических графов и показать существование полиномиального алгоритма поиска хроматического числа для таких графов. 2. Ожидается получение критерия существования почти реберно непересекающихся остовных деревьев в графе и быстрые алгоритмы их поиска. 3. При выполнении проекта предполагается получить классификацию булевых функций от n переменных в классе псевдополиномиальных форм при n ≤ 5 в зависимости от их длины в этом классе, найти максимальную и среднюю длину функций. 4. Планируется построить каталог схем, реализующих функции от n переменных при n ≤ 5, оптимизированных по динамической активности в некоторых основных классах схем проводящего и функционального типа. 5. Предполагается: а) уточнить поведение функции Шеннона для сложности контактных схем классического типа; б) доказать, что в ряде базисов есть возможность построения для «типичной» булевой функции такой реализующей её схемы из функциональных элементов, которая имеет асимптотически оптимальную сложность и линейную динамическую активность; в) установить асимптотическое поведение функции Шеннона для сложности реализации булевых функций в некоторых классах схем программного типа. 6. Предполагается получить асимптотические оценки сложности некоторых систем дискретных функций в классе обобщённых контактных схем. 7. Запланировано получение новой нетривиальной верхней оценки длины минимального единичного проверяющего теста для контактных схем при добавлении дополнительных переменных, а также получение нетривиальных оценок функции Шеннона длины единичного проверяющего теста относительно вставок элементов в схемах из функциональных элементов.

Участниками заявки Селезневой С.Н., Мельник М.В. уже найдена оценка хроматического числа 1-псевдокубических графов и показано существование полиномиального алгоритма поиска хроматического числа для таких графов. Участником заявки Селезневой С.Н. получен порядок максимальной длины булевых функций классе псевдополиномиальных форм. Участниками заявки Ложкиным С.А. и Шуплецовым М.С. ранее был получен ряд оценок функции Шеннона и индивидуальных оценок сложности для функционала динамической активности в некоторых классах схем. Ложкиным С.А. предложены методы синтеза схем, позволяющие получать оценки высокой степени точности для сложности схем. Участником заявки Д.С. Романовым ранее были предложены новые методы синтеза легкотестируемых схем и оценки функций Шеннона дли тестов.