3-SAT, independent set, vertex cover, set cover.
-
Polynomial-Time Algorithm; Certificate t; Efficient(Polynomial) Certifier;
P; NP; NP-Completeness;Algorithm "A" has polynomial running time: if for every input str "s", "A(s)" terminates in at most "O(p(|s|))" steps. where "p(~)" is some polynomial functions.
P problem : all problems "X", for which there exists an polynomial algorithm "A", that solves "X".
B is a efficient (polynomial-time) certifier for problem "X": if (1)B is a polynomial time algorithms that takes two arguments as input, input string "s" and certificate string "t". (2) There exists a polynomial function p so that for every string "s", we have "s in X" iff there exists a string "t", that "|t|<=p(|s|)" (which means not too long), and "B(s,t) == yes".
NP problem : all problem "X", for which there exists an efficient (polynomial) certifier.
**NP-Completeness: ** if all NP problem "Y" can be reduced to an NP problem "X", "X" is NP-Complete.
Suppose X is NP-Complete, X is solvable in polynomial time, if and only if "P = NP".
**How to establish NP-completeness of problem "Y". **:
step1: Show that "Y" is in NP.
step2: Choose an NP-complete problem X.
step3: Prove that "X" can be reduced to "Y".
