##### Question 1: Fixpoint algorithm and inconsistency

Consider a CSP with three variables and three binary constraints:

\(X < Y\)

\(Y < Z\)

\(Z < X\)

and initial domains \(D(X)=D(Y)=D(Z)=[0..100]\).

Assume that all the three constraints are in the propagation queue initially.

Select all the true statements:

The CSP is consistent: it has at least one solution.

The fixpoint algorithm does not detect the inconsistency: it finishes with more than one value in the domain of each variable, and we need to branch and explore a search tree to realize the inconsistency.

The fixpoint algorithm will eventually detect a domain wipe-out and report an inconsistency, but this will take O(n) iterations (executions of propagators), where n is the size of the initial domains of the CSP.

The CSP is inconsistent: it does not contain any solution.

The fixpoint algorithm will detect that the CSP is inconsistent in O(1) time.

##### Question 2: Fixpoint algorithm: general assertions

Select all the true statements regarding the fixpoint computation and implementation in MiniCP:

The number of iterations of each execution of the fixpoint algorithm does depend on the order in which the constraints are executed.

Assuming monotonic propagators, for two different orders of execution of the constraints, the fixpoint algorithm may compute different domains.

In MiniCP the order in which the constraints are executed in the fixpoint algorithm depends on the order in which the user has posted the constraints.

MiniCP has some strategies/heuristics implemented to reduce the length and computation cost of the fixpoint computation.

A good heuristic to reduce computation cost of the fixpoint algorithm is to execute first the cheap (low-complexity) constraints that propagate a lot.

The number of iterations of each execution of the fixpoint algorithm does not depend on the order in which the constraints are executed.

Assuming monotonic propagators, for two different orders of execution of the constraints, the fixpoint algorithm computes the same domains.