|
Прикладная дискретная математика, 2009, номер 4(6), страницы 28–50
(Mi pdm158)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Теоретические основы прикладной дискретной математики
О преобразованиях Цейтина в логических уравнениях
А. А. Семёнов Институт динамики систем и теории управления СО РАН, г. Иркутск, Россия
Аннотация:
В статье сообщается о применении преобразований Цейтина в различных областях пропозициональной логики, связанных с решением систем логических уравнений. Показывается, что преобразования Цейтина не изменяют числа решений системы логических уравнений, и строится биекция между множествами решений системы и результата её преобразований по Цейтину. Приводятся некоторые результаты по применению преобразований Цейтина к построению оценок сложности систем пропозиционального вывода. С использованием преобразований Цейтина строятся простейшие доказательства NP-полноты проблемы совместности системы логических уравнений степени 2 и $\#P$-полноты проблемы подсчёта числа выполняющих наборов для хорновской КНФ. С использованием преобразований Цейтина показывается также, что ROBDD-граф для булевой функции в хорновской КНФ или в КНФ с двухбуквенными дизъюнктами нельзя построить за полиномиальное время, если $P\neq NP$.
Ключевые слова:
логические уравнения, преобразования Цейтина, системы пропозиционального вывода, NP-полнота.
Образец цитирования:
А. А. Семёнов, “О преобразованиях Цейтина в логических уравнениях”, ПДМ, 2009, № 4(6), 28–50
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm158 https://www.mathnet.ru/rus/pdm/y2009/i4/p28
|
Статистика просмотров: |
Страница аннотации: | 1109 | PDF полного текста: | 588 | Список литературы: | 95 | Первая страница: | 1 |
|