Персональные инструменты
 

SAT — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (реплицировано из внутренней CustisWiki)
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
[[SAT]], от ''Satisfiability'', в русскоязычной литературе — «[[Выполнимость]]».
+
[[SAT]], от ''Satisfiability'', в русскоязычной литературе — «Выполнимость».
 
Формулировка задачи:
 
Формулировка задачи:
  

Версия 07:40, 8 декабря 2005

SAT, от Satisfiability, в русскоязычной литературе — «Выполнимость». Формулировка задачи:

Дано булевское выражение, являющееся коньюнктивной нормальной формой (КНФ):

где Kiэлементарные дизьюнкции вида

, , и .

Существует ли (булевский) набор переменных xj, обращающий эту форму в «1» (т. е. в «TRUE»)?

Известно, что задача SATNP-полна.

Известные частные случаи — задачи 3SAT и 2SAT.


Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».

Репликация: База Знаний «Заказных Информ Систем» → «SAT»