Next: The Satisfiability Problem
Up: Notes on Cryptography
Previous: Other uses of the
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.
Translated from LaTeX by Scott Sutherland
1998-03-15