A new approach to address Subset Sum problem

摘要

In this paper, Subset Sum problem (Non Polynomial Complete problem) and analysis of its two solutions is discussed. These solutions are the Dynamic Solution algorithm and the Randomized algorithm. Dynamic Solution is a sound and complete algorithm that can be used to determine satisfiability and unsatisfiability with certainty. Randomized Algorithm can determine satisfiablity as well as the solution if it finds a solution, but it cannot guarantee to find a solution even if there exists one. However, Randomized Algorithm is much faster than iterative algorithm and also finds the solution, which makes it more practical. In addition, analogy between these two algorithms and two other algorithms namely PL-Resolution and Walk-Sat algorithms for 3-CNF SAT problem, which is also NPC problem is discussed and the performance of Randomized Algorithm and WalkSAT Algorithm is acceptable if the problem is not so complex.