The observations reported in this issue have revealed intriguing regularities in the structure of certain NP-complete problems. However they have spawned as many questions as they have provided answers.
In particular, the empirical studies all plot some average or median performance measure against simple structural parameters. Although these plots reveal clear easy-hard-easy patterns they are nevertheless still associated with extremely high variances. In practical terms this means that a random problem instance generated in the supposedly ``hard'' region may not actually be that hard to solve. This suggests that the current parameters used to specify structure in problem ensembles are too crude. Perhaps other, more sophisticated measures of problem structure will prove to have greater discriminatory power. One way to proceed would be to seek out better theoretical understanding of what is responsible for making some problem instances so much harder than others, as discussed in this issue by Hogg and Schrag and Crawford. Another would be to use machine learning techniques [26, 34, 41] to try to discover some useful combination of structural parameters based on the ability to predict the search cost of a set of examples.
A second open issue concerns the range of problems and characteristics over which phase transition behavior is exhibited. To date most of the research has been directed at studies of k-SAT, graph coloring and the traveling salesman problem. In these cases the performance measure of interest has been some measure of computational search cost. However, it would be interesting to learn whether there are any phase transitions, for example, in the quality of the optima found by optimization algorithms [11]. An additional question along these lines is how other signatures of phase transitions manifest themselves in search problems. In many physical phase transitions, the transition marks a change from a disordered to ordered structure, described by some so-called order parameters taking on nonzero values. The ordered phase is characterized by long range correlations among the system's components. Thus we can ask if there are analogies of these characteristics for search problems too.
Another exciting question to explore concerns the range of algorithms, for a particular type of problem, over which phase transition phenomena persist. For example, to date all the algorithms, other than generate-and-test, that have been examined have exhibited a characteristic easy-hard-easy pattern centered at a fixed transition point, including recent observations with hypothetical quantum computers [21]. Indeed this is what makes the phase transition phenomenon so interesting! But other aspects of the phase transition phenomenon, such as the reported anomalously hard cases in easy regions, do appear to be more sensitive to algorithm selection. In particular, in a recent paper by Baker [1] dependency directed backtracking is shown to cure, or at least greatly ameliorate, the occurrence of hard cases in easy regions. This provides yet more evidence that there may be a systematic difference between hard problems in the easy region and hard problems in the hard region [24]. It also points to the use of phase transition results to select different algorithms for different problems based on simple structural properties.
Other applications of the phase transition results concern their relevance for independent or cooperative parallel search [23]. It appears that the nature of information exchanged and the frequency of exchange should be adapted depending on problem structure. But these ideas still need to be developed in detail. Even within the context of a single local search algorithm there is probably useful information embodied in the problem structure to determine an optimal restart time for algorithms such as heuristic repair [40] or GSAT [48], perhaps in conjunction with a statistical sampling of the search space [7]. However, the large variance associated with the current transitions gives only limited improvement as a heuristic for backtracking search methods where initial poor choices can have a major affect on the search cost [20].
The area of phase transitions in computation offers a rich environment for the development of a principled empirical basis for AI. However, we must be careful. We should not focus exclusively on problems simply because they are easy to articulate. The phase transition results have been criticized for merely being artifacts of the particular problem ensembles researchers have used. This seems unlikely due to the robustness of the behavior in a number of different problem ensembles as well as the success of statistical mechanics in describing complex physical systems based on the behavior of idealized models. However, the critics have alerted us to the need to build random problem generators that can be tuned to fit the unique characteristics of real world problems such as job-shop and telescope scheduling, classroom timetabling and some numerical computations [16, 28, 37]. If the statistical insights afforded by phase transition analyses are to be of practical use we will have to evaluate them using problem ensembles that reflect the realities of real-world computation.
We have described the current state of understanding of these phenomena and the deep connections they reveal between structural complexity of problems (measuring how they are represented) and computational complexity of algorithms.