The Backdoor Key: A Path to Understanding Problem Hardness - Ruan, Yongshao; Kautz, Henry; Horvitz, Eric (Proceedings of the Nineteenth National Conference on Artificial Intelligence, AAAI 2004, San Jose, CA., 2004)
We introduce our work on the backdoor key, a concept that shows promise for characterizing problem hardness in backtracking search algorithms. The general notion of backdoors was recently introduced to explain the source of heavy-tailed behaviors in backtracking algorithms (Williams, Gomes, & Selman 2003a; 2003b). We describe empirical studies that show that the key faction,i.e., the ratio of the key size to the corresponding backdoor size, is a good predictor of problem hardness of ensembles and individual instances within an ensemble for structure domains with large key fraction.