Colin P. Williams and Tad Hogg
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com
@INPROCEEDINGS {,
AUTHOR = "Colin P. Williams and Tad Hogg",
TITLE = "Using Deep Structure to Locate Hard Problems",
BOOKTITLE = "Proc. of AAAI92",
PAGES = "472-477",
PUBLISHER = "AAAI Press",
ADDRESS = "Menlo Park, CA",
YEAR = "1992"}
One usually writes A.I. programs to be used on a range of examples
which, although similar in kind, differ in detail. This paper shows how
to predict where, in a space of problem instances, the hardest problems
are to be found and where the fluctuations in difficulty are greatest.
Our key insight is to shift emphasis from modelling sophisticated
algorithms directly to modelling a search space which captures their
principal effects. This allows us to analyze complex A.I. problems in a
simple and intuitive way. We present a sample analysis, compare our
model's quantitative predictions with data obtained independently and
describe how to exploit the results to estimate the value of
preprocessing. Finally, we circumscribe the kind problems to which the
methodology is suited.
postcript (244K)