ВОРОТА | 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 для получения подробной информации.

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

• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
• ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65