|
Автоматика и телемеханика, 1995, выпуск 2, страницы 111–124
(Mi at3571)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Моделирование поведения и интеллекта
Новые классы КНФ, с полиномиально распознаваемым свойством выполнимости
Б. А. Кулик НПО "Аврора", г. Санкт-Петербург
Аннотация:
На основе методов алгебры кортежей [1] разработан алгоритм решения задачи ВЫПОЛНИМОСТЬ КНФ. Доказано, что для класса “плотных” КНФ, у которых “пустые” переменные, не включенные в дизъюнкты, распределены равномерно с вероятностью не более 1/3, сложность этого алгоритма в среднем полиномиальна. Рассмотрены варианты выигрышной стратегии этого алгоритма, позволяющие расширить класс КНФ с полиномиально распознаваемым свойством выполнимости.
Поступила в редакцию: 09.07.1993
Образец цитирования:
Б. А. Кулик, “Новые классы КНФ, с полиномиально распознаваемым свойством выполнимости”, Автомат. и телемех., 1995, № 2, 111–124; Autom. Remote Control, 56:2 (1995), 245–255
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/at3571 https://www.mathnet.ru/rus/at/y1995/i2/p111
|
Статистика просмотров: |
Страница аннотации: | 263 | PDF полного текста: | 141 | Первая страница: | 2 |
|