Расшифровка булевых функций ограниченного весастатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 апреля 2022 г.
Аннотация:Работа посвящена изучению сложности точной расшифровки булевых функций ограниченного веса четырьмя типами запросов: на значение, сравнение, ограниченную и расширенную эквивалентность. Для всех рассматриваемых классов функций получены точные значения сложности расшифровки тремя типами запросов: на значение и на ограниченную и расширенную эквивалентность. Для запросов на сравнение приводятся верхние и нижние оценки, совпадающие по порядку. Помимо этого для класса функций веса, ограниченного только сверху, получена точная оценка сложности расшифровки запросами на сравнение.