@inproceedings{ruan2004the,
author = {Ruan, Yongshao and Kautz, Henry and Horvitz, Eric},
title = {The Backdoor Key: A Path to Understanding Problem Hardness},
booktitle = {Proceedings of the Nineteenth National Conference on Artificial Intelligence, AAAI 2004, San Jose, CA.},
year = {2004},
month = {June},
abstract = {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.},
url = {http://approjects.co.za/?big=en-us/research/publication/backdoor-key-path-understanding-problem-hardness/},
edition = {Proceedings of the Nineteenth National Conference on Artificial Intelligence, AAAI 2004, San Jose, CA.},
}