Clustering at the phase transition

Published 27 July 1997

Andrew Parkes

Citations68

TL;DR

Studying the effect of UPIs on the local search algorithm WSAT shows that these "single-cluster" instances are harder to solve, and this work relates their appearance at the phase transition to the peak in search cost.

Abstract

Many problem ensembles exhibit a phase transition that is associated with a large peak in the average cost of solving the problem instances. However, this peak is not necessarily due to a lack of solutions: indeed the average number of solutions is typically exponentially large. Here, we study this situation within the context of the satisfiability transition in Random 3SAT. We find that a significant subclass of instances emerges as we cross the phase transition. These instances are characterized by having about 85--95% of their variables occurring in unary prime implicates (UPIs), with their remaining variables being subject to few constraints. In such instances the models are not randomly distributed but all lie in a cluster that is exponentially large, but still admits a simple description. Studying the effect of UPIs on the local search algorithm Wsat shows that these &quot;single-cluster&quot; instances are harder to solve, and we relate their appearance at the phase transition to the peak...

Keywords

Computer Science

Where the really hard problems are

1,021 Citations1991Peter Cheeseman, Bob Kanefsky +1 more

It is shown that NP-complete problems can be summarized by at least one "order parameter", and that the hard problems occur at a critical value of such a parameter.

National Conference on Artificial IntelligenceHard and easy distributions of SAT problems

801 Citations1992David G. M. Mitchell, Bart Selman +1 more

It is shown that by using the right distribution of instances, and appropriate parameter values, it is possible to generate random formulas that are hard, that is, for which satisfiability testing is quite difficult.

View PDF

Noise strategies for improving local search

761 Citations1994Bart Selman, Henry Kautz +1 more

It is shown that mixed random walk is the superior strategy for solving MAX-SAT problems, and results demonstrating the effectiveness of local search with walk for solving circuit synthesis and circuit diagnosis problems are presented.

ScienceCritical Behavior in the Satisfiability of Random Boolean Expressions

598 Citations1994Scott Kirkpatrick, Bart Selman

Finite-size scaling, a method from statistical physics, can be used to characterize size-dependent effects near the threshold and a relationship can be drawn between thresholds and computational complexity.

Artificial IntelligenceExperimental results on the crossover point in random 3-SAT

292 Citations1996James M. Crawford, Larry D. Auton

This paper reports on the most extensive set of experiments to date on the location and nature of the crossover point in satisfiability problems, finding no evidence of any hard problems in the under-constrained region.

The constrainedness of search

172 Citations1996Ian P. Gent, Ewan MacIntyre +2 more

A parameter that measures the "constrainedness" of an ensemble of combinatorial problems is introduced, which generalizes a number of parameters previously used in different NP-complete problem classes and can be directly compared.

Artificial IntelligencePhase transitions in artificial intelligence systems

156 Citations1987Bernardo A. Huberman, Tad Hogg

It is predicted that large-scale artificial intelligence systems and cognitive models will undergo sudden phase transitions from disjointed parts into coherent structures as their topological connectivity increases beyond a critical value.

Artificial IntelligenceThe hardest constraint problems: A double phase transition

134 Citations1994Tad Hogg, Colin P. Williams

The distribution of hard graph coloring problems as a function of graph connectivity is shown to have two distinct transition behaviors, including a peak in the median search cost near the connectivity at which half the graphs have solutions.

European Conference on Artificial IntelligenceThe phase transition and the mushy region in constraint satisfaction problems

129 Citations1994Barbara M. Smith

Artificial IntelligenceEasy problems are sometimes hard

127 Citations1994Ian P. Gent, Toby Walsh

It is demonstrated that problem classes and regions of the phase transition previously thought to be easy can sometimes be orders of magnitude more difficult than the worst problems in problem classesand regions ofThe phase transition considered hard.