Subset-Sum Problems and NP-Completeness

- If there is an algorithm which efficiently solves (SSP), it can be used to efficiently solve (SP).
- If there is an algorithm which efficiently solves (SP), it can be used to solve (SSP).
- An algorithm to solve (SP) efficiently would give efficient solutions to factoring and many other problems.

- The Satisfiability Problem
- Converting (SP) to (SSP)
- Converting (SSP) to (SP)
- Cook's Theorem
- Terminology

2002-12-14