|
Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)
Математические основы информатики и программирования
О генерической сложности проблемы общезначимости булевых формул
А. Н. Рыбалов Институт математики им. С. Л. Соболева СО РАН, г. Новосибирск, Россия
Аннотация:
Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В данной работе изучается генерическая сложность проблемы общезначимости (тождественной истинности) булевых формул. Доказывается, что эта проблема неразрешима за полиномиальное время на любом полиномиальном строго генерическом множестве формул при условии её трудноразрешимости в худшем случае.
Ключевые слова:
генерическая сложность, проблема общезначимости булевых формул.
Образец цитирования:
А. Н. Рыбалов, “О генерической сложности проблемы общезначимости булевых формул”, ПДМ, 2016, № 2(32), 119–126
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm547 https://www.mathnet.ru/rus/pdm/y2016/i2/p119
|
Статистика просмотров: |
Страница аннотации: | 193 | PDF полного текста: | 52 | Список литературы: | 32 |
|