Рубрики

ВОРОТА | GATE-CS-2014- (Set-3) | Вопрос 48

Рассмотрим решение задачи 2CNFSAT, определяемой следующим образом:

(A) NP-Complete.
(B) разрешима за полиномиальное время путем сокращения до достижимости ориентированного графа.
(C) разрешимо в постоянном времени, так как любой входной экземпляр выполним.
(D) NP-сложный, но не NP-полный.

Ответ: (Б)
Пояснение: 2CNF-SAT можно свести к проблеме сильно связанных компонентов. И сильно связная компонента имеет полиномиальное время решения. Поэтому 2CNF-SAT разрешимо за полиномиальное время. См. Https://en.wikipedia.org/wiki/2-satisfiability#Strongly_connected_components для получения подробной информации.

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

ВОРОТА | GATE-CS-2014- (Set-3) | Вопрос 48

0.00 (0%) 0 votes