References

1

Andrew B. Baker. Intelligent backtracking on the hardest constraint problems. J. of Artificial Intelligence Research, 1995. to appear.

2

B. Bollobas. Random Graphs. Academic Press, NY, 1985.

3

Tom Bylander. An average case analysis of planning. In Proc. of the 11th Natl. Conf. on Artificial Intelligence (AAAI93), pages 480-485, Menlo Park, CA, 1993. AAAI Press.

4

M. T. Chao and J. Franco. Probabilistic analysis of a generalization of the unit-clause literal selection heuristics. Information Science, 51:289-314, 1990.

5

Peter Cheeseman, Bob Kanefsky, and William M. Taylor. Where the really hard problems are. In J. Mylopoulos and R. Reiter, editors, Proceedings of IJCAI91, pages 331-337, San Mateo, CA, 1991. Morgan Kaufmann.

6

Peter Cheeseman, Bob Kanefsky, and William M. Taylor. Computational complexity and phase transitions. In Proc. of the Workshop on Physics and Computation (PhysComp92), pages 63-68, Los Alamitos, CA, 1992. IEEE Computer Society Press.

7

Pang C. Chen. Heuristic sampling: A method for predicting the performance of tree searching programs. SIAM Journal of Computing, 21(2):295-315, April 1992.

8

James M. Crawford and Larry D. Auton. Experimental results on the cross-over point in satisfiability problems. In Proc. of the 11th Natl. Conf. on Artificial Intelligence (AAAI93), pages 21-27, Menlo Park, CA, 1993. AAAI Press.

9

G. Deutscher, R. Zallen, and J. Adler, editors. Percolation Structures and Processes, volume 5 of Annals of the Israel Physical Society. Adam Hilger, Bristol, 1983.

10

M. E. Fisher and J. W. Essam. Some cluster size and percolation problems. J. Math. Physics, 2(4):609-619, 1961.

11

Jeremy Frank. Phase transitions in NP-hard problem spaces. PhD qualifying exam paper, March 9 1995.

12

M. R. Garey and D. S. Johnson. A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.

13

Ian P. Gent and Toby Walsh. Easy problems are sometimes hard. Artificial Intelligence, 70:335-345, 1994.

14

David L. Goodstein. States of Matter. Prentice-Hall, Englewood Cliffs, NJ, 1975.

15

Craig Gotsman. A cluster detection algorithm based on percolation theory. Pattern Recognition Letters, 12:199-202, April 1991.

16

J. Hasselberg, P. M. Pardalos, and G. Vairaktarakis. Test case generators and computational results for the maximum clique problem. Technical report, Univ. of Florida, 1992.

17

T. Hogg and B. A. Huberman. Artificial intelligence and large scale computation: A physics perspective. Physics Reports, 156:227-310, 1987.

18

Tad Hogg. Phase transitions in constraint satisfaction search. A World Wide Web page with URL ftp://parcftp.xerox.com/pub/dynamics/constraints.html, 1994.

19

Tad Hogg. Applications of statistical mechanics to combinatorial search problems. In D. Stauffer, editor, Annual Reviews of Computational Physics, volume 2, pages 357-406. World Scientific, Singapore, 1995.

20

Tad Hogg. Exploiting problem structure as a search heuristic. Technical report, Xerox PARC, January 1995.

21

Tad Hogg. Quantum computing and phase transitions in combinatorial search. J. of Artificial Intelligence Research, 4:91-128, 1996. Available online at http://www.cs.washington.edu/research/jair/abstracts/hogg96a.html.

22

Tad Hogg and J. O. Kephart. Phase transitions in high-dimensional pattern classification. Computer Systems Science and Engineering, 5(4):223-232, October 1990.

23

Tad Hogg and Colin P. Williams. Solving the really hard problems with cooperative search. In Proc. of the 11th Natl. Conf. on Artificial Intelligence (AAAI93), pages 231-236, Menlo Park, CA, 1993. AAAI Press.

24

Tad Hogg and Colin P. Williams. Expected gains from parallelizing constraint solving for hard problems. In Proc. of the 12th Natl. Conf. on Artificial Intelligence (AAAI94), pages 331-336, Menlo Park, CA, 1994. AAAI Press.

25

Tad Hogg and Colin P. Williams. The hardest constraint problems: A double phase transition. Artificial Intelligence, 69:359-377, 1994.

26

J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, 1975.

27

B. A. Huberman and T. Hogg. Phase transitions in artificial intelligence systems. Artificial Intelligence, 33:155-171, 1987.

28

Mark T. Jones and Paul E. Plassmann. A parallel graph coloring heuristic. SIAM J. Sci. Comput., 14(3):654-669, 1993.

29

Anil Kamath, Rajeev Motwani, Krishna Palem, and Paul Spirakis. Tail bounds for occupancy and the satisfiability threshold conjecture. In S. Goldwasser, editor, Proc. of 35th Symposium on Foundations of Computer Science, pages 592-603. IEEE Press, 1994.

30

P. Kanerva. Self-propagating search: A unified theory of memory. Technical Report CSLI-84-7, Stanford Univ., 1984.

31

R. M. Karp and J. Pearl. Searching for an optimal path in a tree with random costs. Artificial Intelligence, 21:99-116, 1983.

32

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671-680, 1983.

33

Scott Kirkpatrick and Bart Selman. Critical behavior in the satisfiability of random boolean expressions. Science, 264:1297-1301, 1994.

34

John R. Koza. Genetic Programming: On Programming Computers by Means of Natural Selection and Genetics. MIT Press, Cambridge, MA, 1992.

35

Tracy Larrabee and Yumi Tsuji. Evidence for a satisfiability threshold for random 3CNF formulas. In Haym Hirsh et al., editors, AAAI Spring Symposium on AI and NP-Hard Problems, pages 112-118. AAAI, 1993.

36

Manhot Lau and Takashi Okagaki. Applications of the phase transition theory in visual recognition and classifications. J. of Visual Communication and Image Representation, 5(1):88-94, 1994.

37

Gary Lewandowski and Anne Condon. Experiments with parallel graph coloring heuristics. In Proc. of 2nd DIMACS Challenge, 1993.

38

A. K. Mackworth. Constraint satisfaction. In S. Shapiro and D. Eckroth, editors, Encyclopedia of A.I., pages 205-211. John Wiley and Sons, 1987.

39

C.J.H. McDiarmid and G.M.A. Provan. An expected-cost analysis of backtracking and non-backtracking algorithms. In J. Mylopoulos and R. Reiter, editors, Proceedings of IJCAI91, pages 172-177, San Mateo, CA, 1991. Morgan Kaufmann.

40

Steven Minton, Mark D. Johnston, Andrew B. Philips, and Philip Laird. Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence, 58:161-205, 1992.

41

Steven Minton and Ian Underwood. Small is beautiful: A brute-force approach to learning first-order formulas. In Proc. of the 12th Natl. Conf. on Artificial Intelligence (AAAI94), pages 168-174, Menlo Park, CA, 1994. AAAI Press.

42

David Mitchell, Bart Selman, and Hector Levesque. Hard and easy distributions of SAT problems. In Proc. of the 10th Natl. Conf. on Artificial Intelligence (AAAI92), pages 459-465, Menlo Park, 1992. AAAI Press.

43

A. Nijenhuis and H. S. Wilf. Combinatorial Algorithms for Computers and Calculators. Academic Press, New York, 2nd edition, 1978.

44

J. Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, Reading, Mass, 1984.

45

Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, CA, 1988.

46

Patrick Prosser. An empirical study of phase transitions in binary constraint satisfaction problems. Technical Report AISL-49-93, Dept. of Computer Science, Univ. of Strathclyde, Glasgow G1 1XH, Scotland, 1993.

47

Paul Walton Purdom, Jr. Search rearrangement backtracking and polynomial average time. Aritificial Intelligence, 21:117-133, 1983.

48

Bart Selman, Hector Levesque, and David Mitchell. A new method for solving hard satisfiability problems. In Proc. of the 10th Natl. Conf. on Artificial Intelligence (AAAI92), pages 440-446, Menlo Park, CA, 1992. AAAI Press.

49

J. Shrager, T. Hogg, and B. A. Huberman. Observation of phase transitions in spreading activation networks. Science, 236:1092-1094, 1987.

50

Barbara M. Smith. The phase transition in constraint satisfaction problems: A closer look at the mushy region. Technical Report 93.41, Division of AI, Univ. of Leeds, Leeds LS2 9JT, U.K., 1994.

51

H. S. Stone and P. Sipala. The average complexity of depth-first search with backtracking and cutoff. IBM Journal of Research and Development, 30:242-258, 1986.

52

M. S. Waterman, L. Gordon, and R. Arratia. Phase transitions in sequence matches and nucleic acid structure. Proc. Natl. Acad. Sci. USA, 84:1239-1243, 1987.

53

Colin P. Williams and Tad Hogg. Using deep structure to locate hard problems. In Proc. of the 10th Natl. Conf. on Artificial Intelligence (AAAI92), pages 472-477, Menlo Park, CA, 1992. AAAI Press.

54

Colin P. Williams and Tad Hogg. Extending deep structure. In Proc. of the 11th Natl. Conf. on Artificial Intelligence (AAAI93), pages 152-157, Menlo Park, CA, 1993. AAAI Press.

55

Colin P. Williams and Tad Hogg. The typicality of phase transitions in search. Computational Intelligence, 9(3):221-238, 1993.

56

Colin P. Williams and Tad Hogg. Exploiting the deep structure of constraint problems. Artificial Intelligence, 70:73-117, 1994.

57

Ken Wilson. Problems in physics with many scales of length. Scientific American, 241:158-179, August 1979.

58

Weixiong Zhang and Richard E. Korf. An average-case analysis of branch-and-bound with applications: Summary of results. In Proc. of the 10th Natl. Conf. on Artificial Intelligence (AAAI92), pages 545-550, Menlo Park, CA, 1992. AAAI Press.