Problem reduction is a way of solving a problem in AI by replacing it with smaller problems and solving those instead. The structure that records the choices is an AND/OR graph: an AND link means every listed subproblem must be solved, and an OR link means any one alternative will do. A solution is then a whole subgraph in which every AND branch is covered, not a single path from a start state to a goal.
Key takeaways
- In problem reduction, a node is solved when one of its alternative reductions has all of its subproblems solved.
- The AO* procedure, named in Nilsson's textbook, searches AND/OR graphs the way path-search methods search ordinary graphs; its roots are in Martelli and Montanari's 1973 work on additive AND/OR graphs.
- James Slagle's SAINT program, from a 1961 MIT thesis, solved 52 of 54 integrals taken from freshman calculus exams, an early test of this style of problem solving.
- The same AND/OR data structure appears in the Russell and Norvig textbook for plans under nondeterministic actions, where AND nodes stand for the environment's possible outcomes.
- Reduction assumes subproblems can be solved separately; when they interfere, the simple version of the method fails.
A small example from calculus
An integral shows the idea better than a map does. To integrate x squared plus sin x, the sum can be split into two integrals, one of x squared and one of sin x. Both must be solved for the original to be solved, so the split is an AND link. To integrate sin x times cos x, either a substitution or a trigonometric identity will work, and only one needs to succeed, so those two routes form an OR choice. Each subproblem is again an integral, so the same step repeats until every remaining piece is a form that a table of known integrals can answer.
Symbolic integration was an early testbed for programs of this kind. James Slagle's 1961 doctoral thesis at MIT, with Marvin Minsky as advisor, described a heuristic program for it. In the Journal of the ACM paper of October 1963, the abstract reports that the program, running on an IBM 7090, solved 52 of 54 problems drawn from MIT freshman calculus final examinations, at an average of about two minutes each. The result shows how far a heuristic program could go on a task that people learn in a first calculus course.
How reduction differs from searching for a path
| Feature | State-space search | Problem reduction |
|---|---|---|
| What a node stands for | A situation the system can be in | A problem still to be solved |
| What an edge does | Applies one action | Replaces a problem with one or more subproblems |
| What a solution is | A path from start to goal | A subgraph with every AND branch solved |
| When the search ends | A goal state is reached | The root is marked solved |
| Typical question | What is the cheapest route? | Which reductions make everything solvable? |
The water jug and puzzle examples that appear in most introductions are state-space problems, where one sequence of moves is enough. Reduction fits problems that split naturally into parts, such as integration, proving a theorem from lemmas, or planning a job with independent stages.
A traced example with cost updates
The trace below is an illustrative example with assumed numbers, not data from a real system. Each arrow from a node to its children is a connector. Its cost is the sum, over the children, of the child's cost plus one for the arc. A node that is already a known, primitive solution costs zero. Unexpanded nodes carry a guessed cost, which the search later replaces with a computed one. The root G has two connectors: c1 leads to B and C together (an AND), and c2 leads to D alone.
| Step | Action | Updated costs | Best connector at G |
|---|---|---|---|
| 1 | Expand G. Guesses: B = 1, C = 1, D = 4. | c1 = (1+1) + (1+1) = 4; c2 = 4+1 = 5 | c1, cost 4 |
| 2 | Expand B. It has one connector to a primitive solved node, so B = 0+1 = 1 and is marked solved. | c1 = (1+1) + (1+1) = 4 | c1, cost 4 |
| 3 | Expand C. Its connector leads to F and H, each guessed at 2, so C = (2+1) + (2+1) = 6. | c1 = (1+1) + (6+1) = 9; c2 = 5 | c2, cost 5 |
| 4 | Expand D. Its connector leads to two primitive nodes, so D = (0+1) + (0+1) = 2. | c2 = 2+1 = 3 | c2, cost 3, G solved |
Two features of the trace matter. At step 3 the best choice at the root changed because expanding one node raised its true cost above the guess, and the revised value had to travel back up to G. And the final solution never uses B, even though B was expanded and solved. That work was not wasted for correctness, but it shows why such searches track the cost of every alternative instead of committing early.
Where the structure turns up in textbooks and research
The name AO* appears in Nilsson's textbook on AI, whose chapter on decomposable production systems covers searching AND/OR graphs. Survey literature traces it back to the additive AND/OR graph methods that Alberto Martelli and Ugo Montanari presented at the Third International Joint Conference on Artificial Intelligence in 1973, and to their later algorithm HS. The sources checked do not settle how much of AO* was already in the 1973 paper, so credit for it is shared.
The AND/OR idea has a second life in planning. In Russell and Norvig's textbook, the section on search with nondeterministic actions builds an AND-OR search tree in which OR nodes are the agent's choices and AND nodes are the possible outcomes of an action. A solution is a conditional plan that has an answer for every outcome. The graph is the same shape as in problem reduction, but the AND branch has a different meaning: there, all subproblems are parts of one job, and here, they are alternative futures that the plan must survive. Researchers also study AND/OR forward search for contingent planning, which shows that the structure is still in use.
Limits of the method
Reduction works cleanly when the pieces are independent. If solving one subproblem uses up a resource that another needs, or undoes a condition the other relies on, then solving each part in isolation does not produce a valid whole. Another difficulty is cycles: a subproblem that can lead back to itself breaks the simple bottom-up cost update, and a body of research exists on AND/OR graphs with cycles for that reason. Finally, the cost estimates are only as good as the guesses used for unexpanded nodes, which in practice come from domain knowledge.
Questions to ask about any tutorial on the topic
- Does the example state whether each link is AND or OR, or does it draw both with the same symbol?
- Is the cost of an AND link the sum of its children, the maximum, or something else?
- Does the solution it shows include every branch of each AND, or only one path?
- Are the subproblems actually independent in the example?
- Is the algorithm cited to a textbook or paper, with a year, or only described?
FAQ
Is problem reduction the same as divide and conquer?
They are close relatives. Divide and conquer, as taught in algorithm courses, splits a problem into pieces and combines their answers. Problem reduction in AI adds the OR choice among different ways to split, and a search that decides which way to try first.
What does the star in AO* mean?
The sources checked do not explain the naming. The algorithm descends from the HS method of Martelli and Montanari and was renamed AO* in Nilsson's account.
Is AO* the same as A*?
No. A* searches ordinary graphs for a path, while AO* searches AND/OR graphs for a solution subgraph. They share the idea of guiding the search with cost estimates.
Do modern AI systems still use this?
AND/OR search is still used in research on planning under uncertainty, and the Russell and Norvig textbook teaches it. Large neural models do not use it directly.
Related reading
- Three worked examples of formulating an AI problem
- How large AI problem spaces get, from the 8-puzzle to Go
- The water jug problem as state-space search
- What an optimization problem in AI is
More in AI Basics.
Last verified: October 2026
Sources
- Slagle JR, A heuristic program that solves symbolic integration problems in freshman calculus, doctoral thesis, Massachusetts Institute of Technology, 1961, and Journal of the ACM 10(4), 1963
- Martelli A and Montanari U, Additive AND/OR graphs, Proceedings of the Third International Joint Conference on Artificial Intelligence, 1973
- Nilsson NJ, Principles of Artificial Intelligence, Tioga Publishing, 1980 (table of contents as listed by the publisher Elsevier)
- Russell S and Norvig P, Artificial Intelligence: A Modern Approach, chapter 4, section on search with nondeterministic actions (AND-OR search), Pearson
- A Framework for Searching AND/OR Graphs with Cycles, arXiv cs/0305001
- Contingent Planning as AND/OR Forward Search with Disjunctive Representation, International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press