Do solution counts add?

No; counts multiply across independent components.

What if one component has no solution?

The whole problem is unsatisfiable.

Can independence appear after fixing some variables?

Yes; the resulting residual problem may split into separate components, conditional on those assignments.

AI Glossary / Graphs and symbolic AI / Advanced

Independent subproblems

Definition

Independent subproblems are parts of a larger problem that can be solved separately and whose solutions can be combined without additional compatibility decisions. In a constraint satisfaction problem, this requires separate variable groups with no constraint connecting them. Connected components of a correctly constructed constraint graph identify such separations for a binary CSP.

What it means

Dividing work into named tasks does not establish independence. A scheduling problem split by department may still share a room, a person, or an overall capacity limit. Those dependencies can make separately valid schedules incompatible.
Genuine independence is a property of the complete model. Every relevant constraint must belong entirely to one component. For finding a feasible assignment, any solution from each component can then be combined.
Optimization needs an additional check. If the total objective is a sum of component-specific costs, independently minimizing those costs also minimizes their sum. An objective or restriction that couples components may prevent that conclusion even when some local constraints look separate.

How it works

Represent variables as graph nodes and binary constraints as edges. Find the connected components, retain each component's domains and constraints, and solve the resulting smaller problems. If any component has no solution, the whole CSP has no solution.
If every component has a solution, combine the assignments because their variable sets are disjoint and no constraint crosses between them. To enumerate all global solutions, take the Cartesian product of the component solution sets; their counts multiply.
For constraints involving more than two variables, use a representation that preserves the entire constraint scope. A missing edge or an omitted global constraint can create a false appearance of independence.

Three practical examples

A configuration tool chooses options for independent modules. Separate solving is justified only if no shared power, compatibility, or budget requirement links the choices.
A timetable planner separates facilities with distinct rooms, staff, and participants. A person teaching at both facilities would introduce a constraint that prevents treating their schedules as independent.
A document-validation system checks unrelated records using rules confined to each record. A uniqueness requirement across records would create a dependency that local checks alone cannot resolve.

Think of it this way

Think of assembling several puzzles with separate pieces and separate pictures. Each can be completed independently. If two puzzles compete for one shared piece, finishing them separately no longer guarantees that both can be assembled at the same time.

Worked example

Consider six variables A, B, C, D, E, and F. Each has domain {0, 1}. There are exactly three constraints: A must differ from B; C must equal D; and E must be less than or equal to F. No other constraints or objectives apply.
The constraint graph contains three disconnected pairs: {A, B}, {C, D}, and {E, F}. Solve them separately.
The first pair has two solutions: (0, 1) and (1, 0). The second pair also has two: (0, 0) and (1, 1). The third pair has three: (0, 0), (0, 1), and (1, 1).
Choosing any one pair assignment from each list produces a valid full assignment. There are 2 multiplied by 2 multiplied by 3, or 12 global solutions. For example, A = 0, B = 1, C = 0, D = 0, E = 0, F = 1 satisfies every stated constraint.
A simple exhaustive examination of the entire six-variable space considers 2 to the power 6, or 64 assignments. Examining each two-variable component exhaustively considers four local assignments, for 12 local candidates in total. This comparison illustrates reduced search scope; it is not a measured runtime ratio. Listing all 12 global solutions still requires combining and writing those results.
Now add the constraint B = C. The first two components are connected, so their independently selected solutions can no longer be combined arbitrarily. The example assignment above fails because B is 1 while C is 0.
For the four-variable component, B determines the others: A is its opposite, and C and D equal B. Its two solutions are (A, B, C, D) = (1, 0, 0, 0) and (0, 1, 1, 1). Combining either with the three valid E/F assignments gives six global solutions.
The new problem still decomposes, but into {A, B, C, D} and {E, F}.
Finally, suppose the first component also requires A = B while retaining A different from B. That component is unsatisfiable, so no full solution exists, regardless of how many assignments satisfy the other components.

Illustrative case study

Fictional Cedar Scheduling assigns two offices to separate planning agents because their local room lists do not overlap. Each agent returns a schedule that satisfies its own room constraints.
During review, the team notices that a visiting trainer appears in both offices' sessions. The trainer's availability couples the schedules even though the room variables were separated organizationally.
Cedar adds the missing cross-office constraint and recomputes the affected components. Tasks with no shared constraints remain separate, while the trainer's linked sessions are coordinated together.

Common misconceptions and mistakes

“Different variable names prove independence.” Constraints can still link those variables.
“Separate teams imply separate problems.” Shared resources may connect their decisions.
“Solving each part gives an optimal whole.” The objective must also permit the claimed decomposition.
“Disconnected in a diagram means disconnected in reality.” The diagram may omit constraints.
“Independent subproblems means statistical independence.” Here the term concerns solution compatibility, not a probability distribution.

Business use

Before dividing a planning task, list shared resources, cross-record rules, and global requirements. Confirm that the chosen representation includes them. Revisit the decomposition when requirements change.
Measure the largest remaining component as well as the number of components. Many tiny components beside one difficult component may give less speedup than the count suggests. Parallel execution can help, but it is a separate implementation choice; independence can also reduce search when components are solved sequentially.

Check your understanding

Why does the original example have 12 solutions?

Answer: Its component counts are 2, 2, and 3.

What changes when B = C is added?

Answer: Two components become connected and some combinations are excluded.

Why do 12 local candidate checks not prove a runtime ratio?

Answer: Real solving and output have additional costs.

Related terms

Learn next

Add a shared resource constraint to a small scheduling model. Redraw its components and identify which formerly independent assignments now require compatibility checks.

Resource constraint

Sources

AIMA glossary, independent subproblems: https://github.com/aimacode/aima-glossary/blob/master/glossary.md UC Berkeley CS188, CSP structure and decomposition: https://inst.eecs.berkeley.edu/~cs188/fa25/assets/lectures/cs188-fa25-lec05.pdf Poole and Mackworth, constraint reasoning and variable elimination: https://artint.info/3e/html/ArtInt3e.Ch4.S5.html

Previous: Independent multivalued fact Next: Independent variable