В работе оценивается сложность задачи построения приведенных представлений слабо положительных и слабо отрицательных булевых функций, записанных в совершенной конъюнктивной нормальной форме или многочленом Жегалкина.
Скачать электронную версию публикации
Загружен, раз: 106
- Title О СЛОЖНОСТИ НАХОЖДЕНИЯ ПРИВЕДЕННЫХ ПРЕДСТАВЛЕНИЙ СЛАБО ПОЛОЖИТЕЛЬНЫХ И СЛАБО ОТРИЦАТЕЛЬНЫХ БУЛЕВЫХ ФУНКЦИЙ
- Headline О СЛОЖНОСТИ НАХОЖДЕНИЯ ПРИВЕДЕННЫХ ПРЕДСТАВЛЕНИЙ СЛАБО ПОЛОЖИТЕЛЬНЫХ И СЛАБО ОТРИЦАТЕЛЬНЫХ БУЛЕВЫХ ФУНКЦИЙ
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 1(1)
- Date:
- DOI
Ключевые слова
слабо положительная (слабо отрицательная) булева функция , вычислительная сложность Авторы
Ссылки
Dowling W.F., Gallier J.H. Linear-time algorithms for testing the satisfiability of propositional Horn formulae // J. Logic Programming. 1984. No. 3. P. 267 - 284.
Горшков С.П. Применение теории NP-полных задач для оценки сложности решения систем булевых уравнений // Обозрение прикл. промышл. матем., сер. дискрет. матем. 1995. Т. 2. Вып. 3. С. 325 - 398.
Schaefer Т. Complexity of satisfiability problems // Proceedings of the 10 Annual ACM Symposium on Theory of Computing Machinery. 1978. P. 216 - 226.
О СЛОЖНОСТИ НАХОЖДЕНИЯ ПРИВЕДЕННЫХ ПРЕДСТАВЛЕНИЙ СЛАБО ПОЛОЖИТЕЛЬНЫХ И СЛАБО ОТРИЦАТЕЛЬНЫХ БУЛЕВЫХ ФУНКЦИЙ | Прикладная дискретная математика. 2008. № 1(1).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 673