Steepest ascent can be exponential in bounded treewidth problems

David A. Cohen, Martin C. Cooper, Artem Kaznatcheev +1

We investigate the complexity of local search based on steepest ascent. We show that even when all variables have domains of size two and the underlying constraint graph of variabl…