Prove that the problems below are NP-complete. You can assume that the following problems are NPcomplete: 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: T LP = { |G has two paths on at least [n/2] vertices each}

(b) Quarter Partition QP = { |?i, ai ? 0, and a1 ,. . ., an can be partitioned into two disjoint sets S and S and such that ?ai?Sai = ?ai?Sai and, moreover, |S| = [n/4]}

(c) QuadSat: QuadSat = {| ? is a satisfiable 3CNF formula with at least 4 satisfying assignments}.