The Backdoor Key: A Path to Understanding Problem Hardness

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 19

Complexity

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. 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.