In this assignment, you will prove that the Zero Sum problem is NP$-$Complete. The

Zero Sum problem accepts an array of n integers and returns whether it is possible

to negate some of those integers to make the array sum equal $0.$

For example, the array data $=[1,3,5,7,9,11]$ has a zero sum if you negate

the $7$ and $11,$ while the array data $=[1,2,5,9,13,22]$ cannot be reduced to a

sum of zero.

$1.$ Prove that Zero Sum is NP$.$

$2.$ The Subset Sum problem is NPC$.$ This takes in an array of n integers and a

target t to determine if the array has a subset that sums to t$.$

To prove that Zero Sum is NPC$,$ would you reduce Zero Sum to Subset or

Subset Sum to Zero Sum?

$3.$ Give pseudocode for your reduction from question $2$ above.

Subset Sum has two parameters $($an array and a target value$)$ while Zero Sum

only has one $($an array$).$ If you are reducing ZS to SS$,$ you will need to come up

with a target value and possibly modify the array. If you are reducing SS to ZS$,$

you will need to come up with an array that incorporates the target value.

$4.$ Show that your reduction is polynomial time.