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.