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.
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
- The obvious advantage is moving from exponential time to linear time, which is much faster
- It is very rare to be able to separate the problem into independent subproblems