[公告] Algo HW3
Algorithms
Homework # 3
Due: January 10, 2007 (Strict)
1. (25 pts) (Matroid) Exercise 16.4-1, page 398.
2. (25 pts) (2-CNF-SAT) Exercise 34.4-7, page 1003.
3. (25 pts) (NP-completeness) We are given a 3-CNF formula ψ with n
variables and m clauses, where m is even. We wish to determine whether there
exists a truth assignment to the variables of ψ such that exactly half the
clauses evaluate to 0 and exactly half the clauses evaluate to 1. Prove that
such a problem is NP-complete.
4. (25 pts) (NP-completeness) Given a graph and an integer k, is
there a way to color the vertices with k colors such that adjacent vertices
are colored differently? Prove that this problem is NP-complete.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.42.239