Рубрики

Алгоритмы | NP Complete | Вопрос 4

Проблема 3-SAT и 2-SAT являются

(A) как в P
(B) оба NP завершены
(С) NP-завершен и в P соответственно
(D) неразрешимы и NP-завершены соответственно

Ответ: (с)
Объяснение: Проблема булевой выполнимости (SAT) — это проблема решения, чьим примером является логическое выражение, написанное с использованием только AND, OR, NOT, переменных и скобок. Проблема в том, что, учитывая выражение, существует ли какое-либо присвоение значений TRUE и FALSE переменным, которые сделают все выражение истинным? Формула логики высказываний называется выполнимой, если ее переменным можно присвоить логические значения таким образом, чтобы эта формула была истинной.

3-SAT и 2-SAT являются частными случаями k-выполнимости (k-SAT) или просто выполнимости (SAT), когда каждое предложение содержит ровно k = 3 и k = 2 литералов соответственно.

2-SAT — это P, а 3-SAT — NP Complete. (См. Это для объяснения)

Ссылки:
http://en.wikipedia.org/wiki/Boolean_satisfiability_problem

Тест на этот вопрос

Рекомендуемые посты:

Алгоритмы | NP Complete | Вопрос 4

0.00 (0%) 0 votes