Принадлежность классу P задачи проверки выполнимости пропозициональной формулы с заданным значением её скобочной характеристики

Н.К. Косовский, Т.М. Косовская

Результат исследований: Научные публикации в периодических изданияхстатья

Аннотация

Вводится скобочнойая характеристика пропозициональной формулы в базисе из отрицания, многократных конъюнкций, многократных дизъюнкций и многократных эквивалентностей. Доказывается, что задачи проверки выполнимости пропозициональной формулы с любой заранее заданной скобочной характеристикой принадлежат классу {\bf P}. Тем самым получается новое иерархическое разбиение исходной NP-полной задачи выполнимости на подзадачи из класса {\bf P}. При этом каждая задача из иерархии допускает бесконечное множество исходных данных.
Язык оригиналарусский
Страницы (с-по)192-195
ЖурналВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ
Том1(59)
Номер выпуска2
СостояниеОпубликовано - 2014

Ключевые слова

  • пропозициональная формула
  • выполнимость пропозициональной формулы
  • класс {\bf P}.

Цитировать