Next: A probabilistic test for
Up: Subset-Sum Problems and NP-Completeness
Previous: Cook's Theorem
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
1998-03-15