Constraints and Complexity Attack of the Clones约束和克隆的复杂攻击.pptVIP

Presenting Constraints Peter Jeavons Oxford University Computing Laboratory An Abstraction An Abstraction The CSP A set of constraints defines an instance of a constraint satisfaction problem (CSP) General Question Having a general formulation for this kind of problem allows us to ask general complexity questions: Outline Constraint satisfaction problems Constraint languages Complexity of different languages Algebraic properties of constraint languages Expressive power Clones and complexity Half of the Story... This picture illustrates the constraint scopes The set of scopes is sometimes called the constraint hypergraph, or the scheme A lot of work has been done on CSPs with restricted schemes (such as trees) ...The Other Half The picture now emphasises the constraint relations Constraint Languages Definition of CSP(L) Definition 1a: An instance of CSP(L) is a 3-tuple (V,D,C), where V is a set of variables D is a single domain of possible values C is a set of constraints Each constraint in C is a pair (s,R) where s is a list of variables defining the scope R is a relation from L defining the allowed combinations of values The question is whether each variable in V can be assigned a value in D so that all constraints in C are satisfied Alternative Definition of CSP(L) Definition 1b: An instance of CSP(L) is defined to be a first order formula: F = R1(s1) ? R2(s2) ? … ? Rm(sm) where each Ri ? L The question is whether the formula can be satisfied by finding an assignment of values to the variables Another Alternative View Alternative Definition of CSP(L) Definition 1c: An instance of CSP(L) is defined to be a pair of similar relational structures: (V,E1,…,Em) , (D,R1,…,Rm) where each Ri ? L The question is whether there exists a homomorphism from V to D Example If L contains just the binary disequality relation, over the set D = {1,2,…,k}, then CSP(L) is t