0
Я хочу знать, как я могу показать, что 2-CNF не NP-жесткий или NP полный? Может ли кто-нибудь помочь мне в этом отношении. Мне нужно решение срочно.Как я могу доказать, что 2-CNF не является NP-полным?
A
ответ
2
2-CNF выполнимость, как известно, находится в P. Итак, если бы вы смогли доказать, что она не является NP-полной, из этого следует, что P ≠ NP. Таким образом, никто не знает, как это доказать.
Это домашнее задание? –
Если это можно сделать в заранее определенном количестве шагов, то это не NP-Hard или NP-Complete. – Achrome
Попробуйте cstheory.stackexchange.com, но сначала сделайте некоторое усилие. – geoffspear