2. Prove that the problems below are NP-complete. You can assume that the following problems are NP- complete: 3SAT, Hampath. Partition, Clique, and SAT. Make sure you show that the problems are in NP, then give respective reductions and give an "if and only if" argument for reduction correctness as well as say why your reduction runs in polynomial time. (a) Two-Long-Paths: TLP-((G?G has two paths on at least In/2] vertices each} b) Quarter Partition QP -ai,..., an)|Vi,a 2 0, and ai...an can be partitioned into two disjoint sets S and S and such that ?4e5G-?4eai and, moreover, Is-In/4) (c) QuadSat: QuadSat-t(d) ? is a satisfiable 3CNF formula with at least 4 satisfying assignments). (d) k-Clique HamPath: kCHP = {(G,k)|G is an undirected graph and k E N, and G contains both a clique of size k and a Hamiltonian path) (e) Representatives: Rep-S,..., Sm,k)SSm are subsets of some set U with U n k EN, and there is a set S CU, ISI S k, which contains at least one element from each of Si 2. Prove that the problems below are NP-complete. You can assume that the following problems are NP- complete: 3SAT, Hampath. Partition, Clique, and SAT. Make sure you show that the problems are in NP, then give respective reductions and give an "if and only if" argument for reduction correctness as well as say why your reduction runs in polynomial time. (a) Two-Long-Paths: TLP-((G?G has two paths on at least In/2] vertices each} b) Quarter Partition QP -ai,..., an)|Vi,a 2 0, and ai...an can be partitioned into two disjoint sets S and S and such that ?4e5G-?4eai and, moreover, Is-In/4) (c) QuadSat: QuadSat-t(d) ? is a satisfiable 3CNF formula with at least 4 satisfying assignments). (d) k-Clique HamPath: kCHP = {(G,k)|G is an undirected graph and k E N, and G contains both a clique of size k and a Hamiltonian path) (e) Representatives: Rep-S,..., Sm,k)SSm are subsets of some set U with U n k EN, and there is a set S CU, ISI S k, which contains at least one element from each of Si