Given a set of numbers and a target sum, find a subset of numbers where each number in the subset adds up to the target sum.

Example: Given this set {4, 78, 25, 52, 2, 1} and the target sum of 81, two valid subsets exist, {78, 2, 1}, and {4, 25, 52}.

The subset sum problem is classified as bein ing class NP. To prove this, one needs a Turing Machine which can select a subset of numbers, and add them together to see if the sum equals the target sum. This Turing Machine must be able to verify the subset and the sum in polynomial time. The Turing Machine to solve this problem nondeterministically is below

TM SubSum = "on input <S , t>, where S is a set of numbers, and t is a target sum:
1: Nondeterministically select a subset c from S .
2: Test to see if the numbers in c sum to t.
3: If yes, then accept, else reject.
From Michael Sipser's book Introduction to the Theory of Computation.

Log in or register to write something here or to contact authors.