Intro
Computational complexity has said many things to disappoint the possible builders of robots, automated thinkers, knowledge bases, etc. Among these things are that many involved reasoning tasks we would like automated thinkers to perform are not only NP-hard (implying extreme difficulty), but harder. So while good progress has been made on solving certain NP-complete problems like satisfiability in reasonable time (in both practice and in theory, e.g. (Kautz & Selman) and (Schoening) for two ends of this spectrum), these results do not directly help us in performing more substantial inferences.
We consider generalizations for solving these tasks, and also some improvements in search for solving NP-complete problems. Our emphasis is on worst case analysis of our algorithms, though we will take what we can get. We describe strategies for tasks such as circumscription, non-monotonic reasoning, and conditional planning, as well as NP optimization problems. All of these problems (and many others like it) are at least \Sigma_2^P-hard or \Pi_2^P-hard (Eiter & Gottlob), (Rintanen), (Zimand), so any traditional search methods for solving problems in NP will not immediately apply here (unless the polynomial time hierarchy collapses, i.e. pigs fly).
Strategies
We introduce the notion of a "k-legged walk" as a generalization of local search and a viable strategy for solving hard problems in upper levels of the polytime hierarchy. We also give novel ways to perform state space search for SAT solving. Our methods are general/philosophical enough to be applied to virtually any NP-complete problem.
In terms of theoretically proven results, I have recently begun a foray into improved exptime algorithms for counting problems.
Work as part of an M.Eng project with Bart Selman.
References:
T. Eiter and G. Gottlob. Propositional circumscription and extended closed-world reasoning are Pi_2^p-complete. Theoretical Computer Science, 114(2):231-245, 1993.
J. Rintanen. Constructing Conditional Plans by a Theorem-Prover. Journal of Artificial Intelligence Research 10:323-352, 1999.
H. Kautz and B. Selman. Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search. Proceedings of AAAI, 1996.
U. Schoening. A probabilistic algorithm for k-SAT and constraint satisfaction problems. Proceeedings of FOCS, 1999.
M. Zimand. Weighted NP Optimization Problems: Logical
Definability and Approximation Properties. SIAM Journal on Computing
28(1):36-56, 1998.