Open AccessTwo methods of estimation of Boolean bijunctive function weights
Author(s) -
Алексей Вячеславович Тарасов,
А. В. Тарасов
Publication year - 2018
Publication title -
matematičeskie voprosy kriptografii
Language(s) - Russian
Resource type - Journals
eISSN - 2222-3193
pISSN - 2220-2617
DOI - 10.4213/mvk273
Subject(s) - estimation , function (biology) , mathematics , boolean function , statistics , algorithm , biology , evolutionary biology , economics , management
Задача определения веса функции, представимой в виде 2-КНФ (т. е. биюнктивной функции), в общем случае входит в класс труднорешаемых задач перечисления. Однако существуют методы получения верхних и нижних оценок веса таких функций. В работе рассматриваются два метода получения таких оценок: метод включения-исключения и метод, использующий порядковую функцию графа 2-КНФ, представляющей биюнктивную функцию. На основе предложенных методов построен ряд полиномиально вычислимых оценок веса биюнктивных функций.