Extending Deep Structure

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"}

Abstract

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)