Как 2-CNF SAT находится в P, а 3-CNF SAT находится в NPC?

Я действительно не понимаю, почему 2-CNF SAT находится в P, а 3-CNF SAT находится в NPC. Я читал CLRS, и я понимаю, как они доказывают, что 3-CNF SAT находится в NPC. Разве я не могу использовать ту же сводимость от SAT к 2-CNF-SAT, чтобы доказать, что 2-CNF-SAT находится в NPC. Я не понимаю, почему 2-CNF SAT находится в P.

6
задан eejs 7 April 2015 в 11:22
поделиться