3. [20 points] The MaxCut problem is the following: given an undirected graph G (V, E) and an integer k, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets Vi and V2 so that k or more edges have one end in Vi and the other end in V2? (a) Prove that MaxCut is in NP. Carefully, separately, describe the components that are central to the definition of membership in NP (slide 60; KT $8.3): . What, precisely, is the "hint" / "Certificate" / "witness" you envision for this problem? ii. How long is it? iii. What does the "verifier" do with it? In particular, How does the verifier conclude that a specific "hint" proves that this is a "yes" instance of MaxCut, VS What would cause the verifier to conclude that a specific "hint" fails to prove this? Why can't any hint" for a "no" instance "fool" the verifier into saying "yes" when it shouldn't? iv. Asymptotically, as a function of the length of the MaxCut instance and the length of the "hint", how much time does it take to run the verifier? (b) Give an algorithm for MaxCut and analyze its running time. (A non-polynomial-time algorithm shouldn't be a big surprise.) I want moderately detailed proofs/algorithms here, as in my slides concerning the definition of NP (numbered R48-74; see also KT 98.3). Note: Recall that P is a subset of NP. The same facts can be established in almost the same way for the analogous MinCut problem (defined like MaxCut, except