А. А. Вороненко, “О сложности доказательства повторности булевых функций в бинарном базисе”, ПДМ, 2011, номер 3(13),страницы 12

Эта публикация цитируется в 3 статьях

Теоретические основы прикладной дискретной математики

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

А. А. Вороненко

Московский государственный университет им. М. В. Ломоносова, г. Москва, Россия

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

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

УДК: 519.716