nDecision problems:
nphase transitions in solvability, corresponding to hardness spike [Cheeseman et
al.; Selman et al.]
nsolution invariants: e.g., backbone [Gomes et al.]
nOptimization problems:
nexperimental:
•reduce to
decision problem [Zhang et al.]
•introduce
backbone concepts [Walsh et
al.]
ntheoretical:
•polynomial/exponential
transition in search algorithms [Zhang]
•predict A*
nodes expanded for problem distribution [Korf, Reid]
nLearning
ndynamic restart policies [Kautz et al.]