We now give a upper bound on the number of consistency checks performed by HAC in the worst-case. Function can be called at most times for each dual variable , once for every deletion of a value from the domain of , where is one of the original variables constrained with . In each call to the algorithm performs at most checks (one for each value ) to see if is valid (line 17). If is not valid, HAC tries to find a new supporting tuple for in . To check if a tuple that contains the assignment supports we need to check if is valid. If a tuple is not valid then one of its values has been removed from the domain of the corresponding variable. This means that the tuple has also been removed from the domain of the dual variable. Therefore, checking the validity of a tuple can be done in constant time by looking in the domain of the dual variable. The algorithm only needs to check for support the , at maximum, tuples that contain the assignment . Since HAC stores , at each call of and for each value , it only checks tuples that have not been checked before. In other words, we can check each of the tuples at most once for each value of . So overall, in the worst case, we have checks plus the checks to test the validity of the current support. For values the upper bound in checks performed by HAC to make one dual variable AC is =. For dual variables the worst-case complexity bound is , which is the same as the complexity of GAC in the non-binary representation.
The asymptotic space complexity of the HAC algorithm is dominated by the space needed to store the domains of the dual variables. The algorithm also requires space to store the current supports. Since the space required grows exponentially with the arity of the constraints, it is reasonable to assume that the HVE (and the other binary encodings) cannot be practical for constraints of large arity, unless the constraints are very tight.
As mentioned, a consistency check in the non-binary representation is done in a different way than in the HVE. Assume that GAC-2001 looks for a support for value in constraint , where and . A tuple supports if and is valid. To check if is valid, GAC-2001 has to check if values (except ) are still in the domains of variables . Therefore, in the worst case, a consistency check by GAC-2001 involves operations. In contrast, HAC checks for the validity of a tuple in constant time by looking in the domain of the corresponding dual variable to see if the tuple is still there. However, this means that the algorithm has to update the (usually) large domains of the dual variables after a value deletion from an original variable. This affects the run times of the algorithms in different problems settings.
In Appendix A we show that HAC does not only have the same complexity, but it also performs exactly the same number of consistency checks as GAC-2001 in arc consistent problems. We also show that in arc inconsistent problems there can be a difference in the number of checks in favor of the HVE.
Nikolaos Samaras 2005-11-09