Artifact Details

Title

NP-complete problems

Catalog Number

102624710

Type

Moving Image

Date

1993-08-02

Credits

Karp, Richard

Publisher

University Video Communications

Duration

00:38:00

Format

Betacam SP

Copyright Holder

Computer History Museum

Description

From 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."

Category

Lecture

Credit

Gift of University Video Communications

Lot Number

X6636.2013