Tad Hogg and Colin P. Williams
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com
@ARTICLE {,
AUTHOR = "Tad Hogg and Colin P. Williams",
TITLE = "The Hardest Constraint Problems: A Double Phase Transition",
JOURNAL = "Artificial Intelligence",
VOLUME = "69",
PAGES = "359-377",
YEAR = "1994"}
The distribution of hard graph coloring problems as a function of graph
connectivity is shown to have two distinct transition behaviors. The
first, previously recognized, is a peak in the median search cost near
the connectivity at which half the graphs have solutions. This region
contains a high proportion of relatively hard problem instances.
However, the hardest instances are in fact concentrated at a second,
lower, transition point. Near this point, most problems are quite easy,
but there are also a few very hard cases. This region of exceptionally
hard problems corresponds to the transition between polynomial and
exponential scaling of the average search cost, whose location we also
estimate theoretically. These behaviors also appear to arise in other
constraint problems. This work also shows the limitations of simple
measures of the cost distribution, such as mean or median, for
identifying outlying cases.
postcript (806K, 16 pages, available on-line only within Xerox)