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 = "Extending Deep Structure",
BOOKTITLE = "Proc. of AAAI93",
PAGES = "152-157",
PUBLISHER = "AAAI Press",
ADDRESS = "Menlo Park, CA",
YEAR = "1993"}
In a previous paper we defined the deep structure of a
constraint satisfaction problem to be that set system produced by
collecting the nogood ground instances of each constraint and keeping
only those that are not supersets of any other. We then showed how to
use such deep structure to predict where, in a space of problem
instances, an abrupt transition in computational cost is to be expected.
This paper explains how to augment this model with enough extra details
to make more accurate estimates of the location of these phase
transitions. We also show that the phase transition phenomenon exists
for a much wider class of search algorithms than had hitherto been
thought and explain theoretically why this is the case.
postcript (242K)