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.