# Subset Sum is NP Complete

**Prerequisite:** NP-Completeness, Subset Sum Problem

** Subset Sum Problem:** Given

**N**non-negative integers

**a**and a target sum

_{1}…a_{N}**K**, the task is to decide if there is a subset having a sum equal to

**K**.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

** Explanation:** An instance of the problem is an input specified to the problem. An instance of the subset sum problem is a set

**S = {a**and an integer

_{1}, …, a_{N}}**K**. Since an NP-complete problem is a problem which is both in

**NP**and

**NP-hard**, the proof for the statement that a problem is NP-Complete consists of two parts:

- The problem itself is in NP class.
- All other problems in NP class can be polynomial-time reducible to that. (B is polynomial-time reducible to C is denoted as B ≤ P
^{C})

If the **2nd condition** is only satisfied then the problem is called **NP-Hard**.

But it is not possible to reduce every NP problem into another NP problem to show its NP-Completeness all the time. That is why if we want to show a problem is NP-Complete we just show that the problem is in NP and any NP-Complete problem is reducible to that then we are done i.e. if B is NP-Complete and B≤P^{C} for C in NP, then C is NP-Complete. Thus, we can verify that the **Subset Sum Problem** is NP-Complete using the following two propositions:

__Subset Sum is in NP:__

If any problem is in NP, then given a certificate, which is a solution to the problem and an instance of the problem (a set **S** of integer **a _{1}…a_{N} **and an integer

**K**) we will be able to identify (whether the solution is correct or not) certificate in polynomial time. This can be done by checking that the sum of the integers in subset

**S’**is equal to

**K**.

__Subset Sum is NP-Hard:__

In order to prove Subset Sum is NP-Hard, perform a reduction from a known NP-Hard problem to this problem.

Carry out a reduction from which the **Vertex Cover Problem** can be reduced to the **Subset Sum problem**. Let us assume a graph G(V, E) where V = {1, 2, …, N}. Now, for every vertex i, **a _{i}=i**. For every edge (i, j) we define a component called,

**b**.

_{ij}We will represent the integers in a matrix format, where every row is expressed in the base-4 representation of the corresponding integer value of |E|+1 digits.

The matrix has the following properties:

- The first column contains an integer value 1 for
**a**and 0 for_{i}**b**._{ij} - Each of the E columns starting from the right side of the matrix represents a digit for each edge. The column (i, j)=1 for
**a**,_{i}**a**and_{j}**b**, otherwise, it is equal to 0._{ij} - We define a constant k’ such that,

Now, the following propositions hold:

- Let us consider a subset of vertices and edges to (V’, E’) respectively, such that
**b**can contain at most 1 in every column. Also, the k’ parameter has a 2 in all less significant digits up to |E|. We can never have a carry-in these digits. Now, these digits sum up to at-most three 1’s in each column. This implies that for every edge (i, j), V’ must contain either i or j. Therefore, V’ becomes a vertex cover._{ij}

- Let us assume there is a Vertex Cover of size k, we will choose integers
**a**such that i lies in V’ and all_{i}**b**Such that either i or j is in V’. On summation of all these integers in base 4 representation(that we chose from the matrix), we get sum of integers =k’. Therefore, the chosen integers form the subset of integers with sum = k’. Therefore, subset sum holds._{ij}

Let us consider the following example,

Given is a vertex cover V = {1, 3} and k = 2

Now, a_{1} = 1, a_{2} = 2, a_{3} = 3, a_{4} = 4

The matrix can be constructed in the following way:

=>

=>

=>

Now, to prove the value of k’ let us choose **a _{i}** such that i lies in V’, we choose a

_{1}and a

_{3}and

**b**such that either i or j lies in V’, that is we choose

_{ij}**b**such that either i or j is in V’, that is we choose b

_{ij}_{12}, b

_{14}, b

_{23}and b

_{34}from the matrix . In base 4 representation, we have the following values:

a_{1} = 321, a_{3} = 276, b_{12} = 64, b_{23} = 16, b_{14} = 1, b_{34} = 4

These values are computed using the matrix. On summation of these values, we get,

k’ = 321 + 276 + 64 + 16 + 1 + 4 = 682.

Hence, k’ value can be calculated and verified.

Therefore, the **Subset Sum Problem** is NP-Complete.