Доказывается факт взаимно однозначного соответствия между правильными семействами булевых функций и рёберными ориентациями с единственным стоком на булевых кубах. Данное соответствие позволяет перенести часть результатов, полученных для указанных ориентаций, на язык правильных семейств: получить оценки на число правильных семейств длины n ≥ 5 и показать, что задача распознавания правильности семейства является coNP-полной.
Скачать электронную версию публикации
Загружен, раз: 97
- Title О взаимно однозначном соответствии между правильными семействами булевых функций и рёберными ориентациями булевых кубов
- Headline О взаимно однозначном соответствии между правильными семействами булевых функций и рёберными ориентациями булевых кубов
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 48
- Date:
- DOI 10.17223/20710410/48/2
Ключевые слова
правильные семейства булевых функций, рёберные ориентации с единственным стоком, proper families of Boolean functions, unique sink orientationsАвторы
Ссылки
Keedwell A. and Denes J. Latin Squares and their Applications, 2nd Ed. North Holland, 2015. 438 p.
Глухов М. М. О применениях квазигрупп в криптографии // Прикладная дискретная математика. 2008. №2(2). С. 28-32.
Носов В. А. Построение классов латинских квадратов в булевой базе данных // Интеллектуальные системы. 1999. Т. 4. Вып. 3-4. C. 307-320.
Носов В. А. Построение параметрического семейства латинских квадратов в векторной базе данных // Интеллектуальные системы. 2006. Т. 8. Вып. 1-4. С. 517-529.
Szabo T. and Welzl E. Unique sink orientations of cubes // Proc. 42nd IEEE Symp. FOCS. Newport Beach, CA, USA, 2001. P.547-555.
Schurr I. Unique Sink Orientations of Cubes. Doctoral Thesis. ETH Zurich, 2004.
Носов В. А., Панкратьев А. Е. О функциональном задании латинских квадратов // Интеллектуальные системы. 2008. Т. 12. Вып. 1-4. С. 317-332.
Gartner B. and Thomas A. The complexity of recognizing unique sink orientations // Leibniz Intern. Proc. Informatics (LIPIcs). 2015. V. 30. P.341-353.
Matousek J. The number of unique-sink orientations of the hypercube // Combinatorica. 2006. V. 26. P. 91-99.
О взаимно однозначном соответствии между правильными семействами булевых функций и рёберными ориентациями булевых кубов | Прикладная дискретная математика. 2020. № 48. DOI: 10.17223/20710410/48/2