Terminology

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.