c*w
发帖数: 4736 | 1 given CNF-satisfiability prob. is NP complete, proove 3-CNF
satisfiability problem is NPC:
step1. Proove 3-CNF is NP, i.e., there exists a nondeterministic
turing machine that could solve the problem in polynomial time.
trivially, if the there's already a satisfiable boolean
configuration, then the turing machine only needs linear time to
proove it's right.
step2. the CNF-S could be reduced to 3-CNF-S.
consider one clause (a b c d e) construct 3-CNF in this way:
(a b x) And (Not(x) c y) And (Not |
|
