Consider the complexity for generalized arc consistency beyond the binary case considered in the text (page 140). Suppose there are n variables, c constraints, where each constraint involves k variables, and the domain of each variable is of size

d. How many arcs are there? What is the worst-case cost of checking one arc as a function of

c, k, and d? How many times must an arc be checked? Based on this, what is the time complexity of GAC as a function of

c, k, and d? What is the space complexity?