Algorithm Complexity
NTT Communication Science Labs.
worst-case time complexity:
- exponential in n
- CSPs in general are NP-complete problems.
worst-case space complexity:
- exponential in n
- determined by the number of recorded nogoods
- The number of recorded nogoods can be restricted in practice.
- For all of the example problems, the algorithm was able to find a solution when the number of recorded nogoods was restricted to 10.