** Next:** A probabilistic test for
** Up:** Subset-Sum Problems and NP-Completeness
** Previous:** Cook's Theorem
** Contents**

The concept we have vaguely described as
solving efficiently is technically known as ``polynomial time.''
The types of problem that can be considered as ``guess and verify''
are called NP (for Nondeterministic [the guessing stage] Polynomial
[the verification stage]). Cook's Theorem says that (SP) is as hard
as any NP problem-- the usual terminology is to say (SP) is NP-complete.
Since we showed in section 5.2 that (SSP) could be used to solve
(SP), we essentially proved that (SSP) is also NP-complete.

*Computers and Intractability*, by Garey and Johnson, is strongly
recommended for more information.

*Translated from LaTeX by Scott Sutherland *

2002-12-14