Показано, что для доказательства повторности булевой функции в базисе всех функций двух переменных в худшем случае требуется линейное по числу переменных функции количество наборов.
Скачать электронную версию публикации
Загружен, раз: 80
- Title О сложности доказательства повторности булевых функций в бинарном базисе
- Headline О сложности доказательства повторности булевых функций в бинарном базисе
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 3(13)
- Date:
- DOI
Ключевые слова
proof complexity, read-once Boolean function, сложность доказательства, бесповторная булева функцияАвторы
Ссылки
Вороненко А. А. О проверяющих тестах для бесповторных функций // Матем. вопросы кибернетики. Вып. 11. М.: Физматлит, 2002. С. 163-176.
Перязев Н. А. Слабоповторные булевы функции в бинарном базисе // Дискретная математика и информатика. Вып. 4. Иркутск: Изд-во Иркут. ун-та, 1998. 12 с.
Стеценко В. А. О предплохих базисах в P2 // Матем. вопросы кибернетики. Вып. 4. М.: Физматлит, 1992. С. 139-177.
О сложности доказательства повторности булевых функций в бинарном базисе | Прикладная дискретная математика. 2011. № 3(13).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 248