Question

Given a set S of integers, we say that S can be partitioned if it can be split into two sets U and V so that considering all u  U and all v  V, u = v. Let PARTITION = { <S> | S can be partitioned }.

a. (5) Show that PARTITION  NP by writing either a verifier or an NDTM.

b. (15) Show that PARTITION is NP-complete by reduction from SUBSET-SUM.

9.(20) Given a set of integers, we say that can be partitioned if it can be split into two sets U and V so that considering all u EU and all v € V, Eu = Ev. Let PARTITION = {<> S can be partitioned }. a. (5) Show that PARTITION € NP by writing either a verifier or an NDTM. b. (15) Show that PARTITION IS NP-complete by reduction from SUBSET-SUM.

Answer 1

ANSWER:
and unv= ф the う a) PARTITION END : Hence is a polynomial -time verifier fore PARTITION: *V = n on isput <31Uv): * Check that (UJUV) s ( where ut union and an interesection) * check seem of elements in u equals the sum of elements in. v. * It so accept : Othere wese , teeject. By given condition Eu= Ev , tutu & vet Hence, PARTIOTION AND Ore the pare te tion problem es in the class Np. b) by even & show that PARTITION es up-complete by reeduction from SUBSET-SUM 1) There is a non-deferemeno polynomial-time algorithe that solves A is Ae.Np. 18). Any Np - compuede poobley B can be reduced to 4. el) The reduction of B to A works in polynomeau teme. iv) The Original problem. A has a has a soluteom of and only of B has a soketom. We know's show that SET-PARTITION o Np-compute Ite easy SET - PARTITION 2 be verified en polynomial time; ༡ to see that

) ously a Given partitions U V jest sum the two and verify that theire sum. equals each other, which als obrer a polynoudon the tinje vend tocatlon. (Because summation as a polynoycay operation and we hance performing at most 1 sl many sremmate on The core of the proof &s en reeadacing SUBSET ETT EUM to PARTITION, To that end geven eet'e and a value Volthe subet som query we form a new set sl-su{x-24}, wheree E a че е To see that this is a reduction. (7) Assume theree erists some pes seech that t-Ex then We would have that x-t EX xep us x-2t} 1 х nep x-t Z a XES' and we would have that U. X-26 paretetion of sl. (*) suppose that s! such that there is a pare te telon Pis P of En la rep KER

par to thon 9 Notice that thee Endverels @ natural P, and P2 of s, such that WLOG we have that X-24 t Exs In XEpi xepi X-2t tłnit. Ex. xep nepi Eatła 2X KEP, KEP, s-2t + 2E a=X nepi 3) I not nep, Hence, from a sole from Poletion - Ex we con nep a parte ton Pit pu{x-2+} s'll pu { x^2+11) P2 = 5 con can from xepi and nversely from a pare te teug Pili Pa' we Solution t= En -21.2 there force the happing : (site is a reedu reeduction (Because tset) is the language feet LUBLET ETSUM 2 sl = f(sit) is the language / set (posete toon). PARTITION !

م And it is clear to see that the transformation was done in polejno real time. TIPTON Es Np - computea Hences PART s 03