New Techniques in Design and Analysis of Exponential Algorithm Arshi Aftab, Shikha Mahajan and Shruti Jajoo

Abstract: In this paper we first see how NP problems can be categorized and look at some examples. We then analyze the subset sum problem and prove its NP completeness. We look at various algorithms used to solve the problem and the efficiency of each algorithm. Hence we prove that subset sum problem is NP complete.
Keywords: NP complete, NP hard, complexity, subset sum, exponential I. Introduction
In the study of computation complexity of problems, we find out the resources required during computation like time, memory and space required. We check if the problem can be solved in polynomial time by some algorithm. An algorithm is said to be solved in polynomial time if its worst case efficiency belongs to O (p (n)) where p (n) is the polynomial of the problems input size. Problems that can be solved in polynomial time are called tractable and those that cannot be solved in polynomial time are intractable.
The formal definition of NP problem is as follows: A problem is said to be Non-deterministically Polynomial (NP) if we can find a nondeterministic Turing machine that can solve the problem in a polynomial number of nondeterministic moves.
Equivalent definition of NP problem: A problem is said to be NP if
1. its solution comes from a finite set of possibilities, and
2. It takes polynomial time to verify the correctness of a possible solution.
NP-complete problems
NP-complete problems are a subset of class NP. An problem p is NP-complete, if
1. p ∈ NP (you can solve it in polynomial time by a non-deterministic Turing machine) and
2. All other problems in class NP can be reduced to problem p in polynomial time.
NP-hard problems
NP-hard problems are partially alike but more difficult problems than NP complete problems. They don’t themselves belong to class NP (or if they do, nobody has invented it, yet), but all problems in class NP can be reduced to them. Very often, the NP-hard problems require exponential time or even worse. Figure 1.1

Some of the well-known problems which fall into the category of NP problems are:
1. Hamiltonian circuit: to determine where a graph has a Hamiltonian circuit. (A circuit which covers all the vertices of a graph.)
2. Integer linear programming: To find the optimal (maximal or minimum) solution of linear function subject to a finite set of constraints in the form of linear equalities or inequalities.
3. Travelling Salesman problem: To find the shortest Hamiltonian circuit in a complete graph with positive integer weights.
4. Partition Problem: Determining whether it is possible to partition a set of n positive integers into two disjoint subset of the same sum.
5. Knapsack problem: To find the set of most valuable items among n items of given positive weight and value that fit into a knapsack of given positive integer capacity.
6. Graph coloring: To find the chromatic number of a given graph
In our paper we aim to show that the subset sum problem belongs to the NP class.
The subset sum problem in computer science is noteworthy problem in complexity theory and cryptography. It can be defined as: Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Example 1.1
Set [] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True //There is a subset (4, 5) with sum 9.
The complexity of a problem can be analyzed depending on two parameters: N, number of decision variables and P, precision of the problem. The complexity of best known algorithms is exponential or in other words the problem is difficult if both N and P are of same order. The solution becomes compatible when either N or P has smaller value. If N is small then exhaustive search can give a better solution and if P has a smaller value then dynamic problem algorithms can give the exact solution. The algorithms which provide an efficient time complexity are introduced and elaborated in the next section.
II .Methodology
2.1 NP Completeness of Subset Sum Problem
The merest requisite for an algorithm to be considered as efficient is that its time efficiency should be polynomial[2]: O(n^c),for some constant c and n is the size of the input. Scientists remarked on this point long ago that most of the real time currently existing problems be figured out this quickly, but they said that they had a tough time unraveling which problems could and which could not. There are a considerable number of so called NP-hard problems which most people deem that its solution cannot be computed in polynomial time, nevertheless nobody could justify a super-polynomial lower bound.
Generally, given a set of numbers S {s1,s2,s3,……., son} and a target number t, the objective is to find a subset S’ of S such that the elements in it sum up to t. Although the proposed problem appears deliberately facile, solving it is exceedingly tough if not provided with any additional instruction. It would be established later that it is an NP-complete problem and possibly an efficient algorithm may not exist at all.
2.1.1 Problem Definition
The decision statement of the problem is: Given a set S and target t ,does there prevail a subset such that .
2.1.2 Exponential Time Algorithm Approaches:
One exceptional feature to be noted about this problem is that the problem becomes polynomial if the size of S’ is given. For instance an exemplary question may be: Given a cluster of numbers we have to find two elements such that they add up to t. This problem is entirely polynomial and we can come up with a candid algorithm with running time O(n^2) and with nested foe loops.
There can be considerably one more convoluted problem asking for ,say, 3 elements that sums to t. Again, we can try to achieve a solution with an ingenuous approach of complexity . The catch in the generic part of subset sum is that we do not know . At the worst case is and hence the running time of brute force approach is approximately .
A slightly higher efficiency algorithm tries to find out all the desirable .There is a symbolic way in which this can be done, that is all numbers from 0 to can be intended in binary representation and thus a subset of elements could be generated whose indexes are equal to the bit positions that correspond to 1.For instance if n is 4 and let the given number in decimal be 10 and its binary representation is 1010.The next step is that we go through the subsets wherein lies the 1st and the 3rd elements of S. The boon of this kind of approach is that it uses a homogeneous amount of space. At every repetition ,we read a particular number ,thus leading to a deliberate result if |S’| is small in value.
Let us ponder over the case where . We have to investigate and figure out around distinct subsets in order to obtain this solution .A somewhat different way discovers all probable sums of subsets and examines if t has appeared in the subset
2.2 Algorithms to Solve Subset Sum Problem
2.2.1 Polynomial-Time Approximate Algorithm
A polynomial time approximation scheme (PTAS) is an algorithm that takes as input not only an instance of the problem but also a value ε > 0 and approximates the optimal solution to within a ratio bound of 1 + ε. For any choice of ε the algorithm has a running time that is a polynomial in n, the size of the input. A fully polynomial-time approximation scheme (FPTAS) is a PTAS with a running time that is polynomial not only in n but also in 1/ε.
3.1 Trim Subroutine for Approximate Subset Sum Algorithm
Let L{x1, x2, . . . , xm} be a list. If several values in L are close to each other, maintain only one of them, i.e. we trim each list Li after it is created. To trim the list by parameter δ means to remove as many elements from L as possible in such a way that the list L’ of remaining elements has the following property:
For every y ∈ L there exists a z ∈ L’ such that (1 − δ) y ≤ z ≤ y.
Algorithm: Trim (L, δ)
1. m