AI Meets the Real World: Applying Weak Methods to Practical Problems

Matthew L. Ginsberg
CIRL, University of Oregon


The conventional wisdom in AI (even as taught at Stanford) is that NP-complete problems are intractable in general.

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.

About the Speaker

Matthew L. Ginsberg received his doctorate in mathematics from Oxford in 1980 at the age of 24. He remained on the faculty in Oxford until 1983, doing research in mathematical physics and computer science; during this period, he wrote a program that was used successfully to trade stock and stock options on Wall Street.

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.
Back to the Colloquium Page
Last modified: Tue Oct 19 21:59:46 PDT 1999