The Backdoor Key: A Path to Understanding Problem Hardness

Yongshao Ruan, Henry Kautz, and Eric Horvitz

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.