Determining if (FC-) (conflict-directed) backjumping visits a given node is NP-hard

摘要

Conflict-directed backjumping is a modification of the backtracking algorithm that can outperform forward checking in non-pathological examples. We prove it is in general NP-hard to determine if backjumping or conflict-directed backjumping or their forward checking hybrids visit a given node of a search space. This shows that these algorithms are fundamentally more complex to analyze than backtracking and forward checking. We conclude by describing how similar results can be proved for versions of the Maintaining Arc Consistency algorithm.