Cs188AI Wiki

General Info[]

T can be seen as an independent subproblem

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

Advantages[]

  • The obvious advantage is moving from exponential time to linear time, which is much faster

Disadvantages[]

  • It is very rare to be able to separate the problem into independent subproblems