next up previous contents
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