Subset-Sum Problems and NP-Completeness

The phrase ``NP-complete'' has an intimidating sound. In this section, we will first define a new problem involving formulas in logic, called the Satisfiability Problem (SP). We will use the abbreviation (SSP) for the subset-sum problem. Our main results will be:

1.

If there is an algorithm which efficiently solves (SSP), it can be used to efficiently solve (SP).

2.

If there is an algorithm which efficiently solves (SP), it can be used to solve (SSP).

3.

An algorithm to solve (SP) efficiently would give efficient solutions to factoring and many other problems.