Complexity of Constraint Propagation Assume domains are of size at most d .there are e binary constraints Complexity Straight forward arc consistency is o(ed3) There are 2*e arcs to check Verifying arc consistency takes o(d2) for each arc An arc is checked at most o(d)times Is arc consistency sound and complete? Each arc consistent solution selects a value for every variable from the arc consistent d Completeness: Does arc consistency rule out any valid solutions? Soundness: Is every arc-consistent solution a solution to the csP? Yes R. G33 Complexity of Constraint Propagation Assume: • domains are of size at most d •there are e binary constraints. Complexity: • Straight forward arc consistency is O(ed3) • There are 2 * e arcs to check • Verifying arc consistency takes O(d2) for each arc. • An arc is checked at most O(d) times. 34 Is arc consistency sound and complete? R, G R, G R, G Each arc consistent solution selects a value for every variable from the arc consistent domains. Completeness: Does arc consistency rule out any valid solutions? •Yes • No Soundness: Is every arc-consistent solution a solution to the CSP? • Yes • No