
| Name of            | Worst case                         | Worst case       |              |           |      |       |      |     |
|--------------------|------------------------------------|------------------|--------------|-----------|------|-------|------|-----|
| the algorithm      | time complexity                    | space complexity |              |           |      |       |      |     |
| A C                | Bessière Freuder                   | Regin            | 0 ed 2 1 8 1 | 0 ed      |      |       |      |     |
| RPC                | De bruy ne                         | ed               | cd 2 (*)     | 0 ed      |      |       |      |     |
| a                  | 0 en                               | cd               |              |           |      |       |      |     |
| Max RPC  Debruy ne | Bessiere                           | 0 en             | ed 2         | cd³ (*)   | 0 ed | cd    |      |     |
| PC                 | Sing h                             | O n 3 d 3 ( 8 )  | 0 n 3 d 2    |           |      |       |      |     |
| PC                 | Chmeiss                            | Jegou            | 0 n 3 d 4    | 0 n 2 d 2 |      |       |      |     |
| PIC                | Freuder                            | Elfe             | 0 en d       | O n       |      |       |      |     |
| PIC                | De bruy ne                         | 0 en             | ed 2         | cd 3 (*)  | 0 ed | c d   |      |     |
| Freuder            | Elfe                               | On               |              |           |      |       |      |     |
| NIC                | 0 g 2 n                            | ed do +1         |              |           |      |       |      |     |
| SAC                | Debruy ne                          | Bessiere         | 0 en2d       | 0 ed      |      |       |      |     |
| b                  |                                    |                  |              |           |      |       |      |     |
| SRPC               | Debruy ne                          | Bessiere         | b            | 0 en      | n² e | c d ' | 0 ed | c d |
| (*)                | optimal worst case time complexity |                  |              |           |      |       |      |     |

of pairs of values in that algorithm Many other singleton consistencies can be considered since any local consistency can be used to detect the possible inconsistency of the CNs P|Di={a} with i, a E D If a local consistency can be enforced in a polynomial time the corresponding singleton consistency also has a polynomial worst case time complexity The formal definitions of the local consistencies studied in this paper are presented in Fig ure Table recalls the time and space complexities of the most efficient algonthms enforcing them The worst case time complexity of SAC SRPC and NIC have not been proved to be optimal

## 4. Relations Between Pic, Rpc And Max-Rpc

To highlight the relations between PIC RPC and Max RPC let us show a property of path inverse consistency  As shownin  Debruy ne if we assumethat the constraint network is arc consistent enforcing PIC requires checking even less tuples than those mentioned in Freuder   Elfe If  i, a  is arc consistent  it can be extended to any   tuple  i, j, k such that there is no constraint between j and k Indeed  i,a has asupport j,b on Cj, and a support k, c on C i k and since j is not linked to k o i, a , j, b , k, c o is consistent Furthermore i, a can be extended to i, j, k if there is no constraint between i and k resp  between i and j   Indeed   i, a  has a support b in D j  resp  c in D k  and this value being arc consistent too it has a support c in D k  resp  b in D j   So   i, a , j, b , k,c is consistent Consequently if the constraint network is arc consistent the only t uples that have to be checked to achieve PIC correspond to the cliques of the constraint graph