PublisherUniversity Video Communications
Copyright HolderComputer History Museum
DescriptionFrom University VIdeo Communications' catalog:
"ACM's A.M. Turing Award winner Richard Karp clearly defines NP-complete problems. A combinatorial search problem involves searching through a finite, but very large, set of possible patterns or arrangements for one that satisfies a stated set of constraints. Despite decades of effort, many important combinatorial search problems seem intractable, since every known algorithm for their solution experiences a combinatorial explosion in running time as the problem size increases."