In practice, however, this is simply wrong: NP-complete problems are typically easy and almost always tractable. This suggests (correctly, I would argue) that the computational problems of intelligence can best be addressed by finding and solving NP-complete approximations of them.
In this talk, I discuss this overall approach, describing leading methods for solving satisfiability problems and considering the main difficulty encountered by these methods: The NP-complete problems associated with difficult realistic problems are awkwardly large. I present a new technique that can reduce both the size of the problems and the time needed to solve them by multiple orders of magnitude.
Ginsberg's continuing interest in artificial intelligence brought him to Stanford in late 1983, where he remained for nine years. He then went on to found CIRL, the computational intelligence research laboratory at the University of Oregon, which he directed until 1996. Ginsberg's present interests include constraint satisfaction, planning, and computer bridge. He is the author of numerous publications in these areas, the editor of "Readings in Nonmonotonic Reasoning," and the author of "Essentials of Artificial Intelligence," both published by Morgan Kaufmann. He is also the author of the bridge-playing program GIB, which recently made international news by participating in the world bridge championships in Lille, France, and the CEO of On Time Systems, Inc., CIRL's commercial scheduling spinoff.