## General Info

### What

An independent subproblem is an extreme and very desirable case of structure in a constraint satisfaction problem. It occurs when no element in a set of constrained variables is constrained with another set of constrained variables.

### Implications

Note: The total number of ways to assign a csp with variables and values in the domain of each variable is on the order of

• If there are variables and we can isolate them into independent subproblems, where is the number of variables in each subproblem, then we can solve the entire csp in time , assuming there are values in the domains of the variables. This time is linear in
• If we do not isolate the problem and solve it in the traditional way, we could end up with time . This time is exponential in