The complexity of constraint satisfaction revisited

摘要

This paper is a retrospective account of some of the developments leading up to, and ensuing from, the analysis of the complexity of some polynomial network consistency algorithms for constraint satisfaction problems.