Divideandconquer 浙江大学计算机科学与技术学院分治浙江大学计算机科学与技术学院.ppt

NP and ComputationalIntractability 叶德仕 yedeshi@ Decision Problems Decision problem. (the answer is simply yes or no ) X is a set of strings. Instance: string s. Algorithm A solves problem X: A(s) = yes iff s ∈ X. Optimization problems. in which each feasible (i.e., legal) solution has an associated value, and we wish to find the feasible solution with the best value. Polynomial time. Algorithm A runs in poly-time if for every string s, A(s) terminates in at most p(|s|) steps, where p(.) is some polynomial. Certification algorithm intuition. Certifier views things from managerial viewpoint. Certifier doesnt determine whether s ∈ X on its own; rather, it checks a proposed certificate t that s ∈ X. i.e., certifier verify the proposed solution t and the instance s whether C(s,t) is yes. Def. Algorithm C(s, t) is a certifier for problem X if for every string s, s ∈ X iff there exists a string t such that C(s, t) = yes. NP. Decision problems for which there exists a poly-time certifier. Remark. NP stands for nondeterministic poly-time. Certifiers and Certificates: Composite (合数) COMPOSITES. Given an integer s, is s composite? Certificate. A nontrivial factor t of s. Note that such a certificate exists iff s is composite. Moreover |t| ≤ |s|. Certifier. boolean C(s, t) { if (t ≤1 or t ≥ s) return false else if (s is a multiple of t) return true else return false } Example Instance. s = 437,669. Certificate. t = 541 or 809. Conclusion. COMPOSITES is in NP. Certifiers and Certificates: 3-Satisfiability SAT. Given a CNF formula ?, is there a satisfying assignment? Certificate. An assignment of truth values to the n boolean variables. Certifier. Check that each clause in ? has at least one true literal. Certifiers and Certificates: Hamiltonian Cycle HAM-CYCLE. Given an undirected graph G = (V, E), does there exist a simple cycle C that visits every node? Certificate. A permutation of the n nodes. Certifier. Check that th