Outline What is a constraint satisfaction problem(CSPS)? Solving cSPs Arc-consistency and propagation Analysis of constraint propagation · Search What is the Complexity of Constraint Propagation? Assume domains are of size at most d .there are e binary constraints Which is the correct complexity? 1.O(d 3.O(ed3) 4.O(e)31 Outline • What is a constraint satisfaction problem (CSPS)? • Solving CSPs • Arc-consistency and propagation • Analysis of constraint propagation • Search 32 What is the Complexity of Constraint Propagation? Assume: • domains are of size at most d •there are e binary constraints. Which is the correct complexity? 1. O(d2) 2. O(ed2 ) 3. O(ed3) 4. O(ed)