NP-complete problems

"Where the Really Hard Problems Are".

Reprint of the paper from the IJCAI-91 proceedings as hypertext, TeX, or PostScript (no figures). and the slides from the presentation. The slides are linked to the hypertext and vice versa.

Later Research

• Cheeseman, Taylor, and others have done extensive followup work. This will probably be put on the WWW in the future.
• Kanefsky did an empirical test of the claim depicted in Slide 10 about what the search trees look like. The tree drawings generated may be put on the WWW someday if he gets a chance to adapt the code.