Does a complete search guarantee that a solution exists?

No. It guarantees finding one if one exists under the stated conditions.

Is completeness the same as soundness?

No. Completeness concerns missed consequences; soundness concerns unjustified conclusions.

Does a timeout prove infeasibility?

No. Unless a separate proof was completed, the search may simply remain unresolved.

AI Glossary / Graphs and symbolic AI / Intermediate

Completeness

Definition

Completeness is a guarantee that a method can find every kind of result it is intended to find within a specified formal scope. A search algorithm is complete if it finds a solution whenever one exists under its assumptions. A logical inference system is complete if every consequence in its stated scope can be derived using its rules.

What it means

The word always needs a reference point: complete for which problems, language, result type, and operating conditions? An unqualified claim can hide important restrictions.

In search, the concern is avoiding failure to find an existing solution. In inference, the concern is avoiding gaps between what follows semantically from the premises and what the proof rules can establish. These meanings are closely related but not identical.

Completeness is also different from having complete data or a complete assignment. Those describe whether information or variable values are present. Here the term concerns the coverage of a method's formal capabilities, not how fully a record or candidate is filled in.

How it works

A search completeness argument usually explains why a solution cannot remain permanently unexplored. Breadth-first search, for example, explores progressively deeper levels. With finite branching and a solution at finite depth, it eventually reaches that depth.

A depth-first tree search can instead follow an infinite branch while a solution waits elsewhere. On a finite graph, appropriate repeated-state handling changes the analysis, so the assumptions must be stated rather than assigning a universal label from the algorithm's name alone.

For logical inference, write semantic consequence as 'the conclusion holds in every model of the premises.' Completeness asks whether the proof system can derive every such conclusion in its stated language. Soundness asks the reverse question: whether every derivable conclusion really follows.

A complete proof calculus does not make every implementation complete under every search strategy. The procedure must explore relevant proof opportunities appropriately. Resource limits can also interrupt a method before its theoretical guarantee has time to apply.

Three practical examples

1. A planning team checks whether a proposed search method can miss an existing plan because it permanently discards unexplored alternatives.

2. A theorem-proving researcher distinguishes the completeness of inference rules from the behavior of a particular proof-search strategy.

3. A solver interface distinguishes an established no-solution result from a timeout, avoiding an unsupported conclusion that a feasible candidate does not exist.

Think of it this way

Think of a search procedure for a building that systematically visits every relevant room. If the desired item is in one of those rooms and the procedure finishes the necessary visits, it will be found.

The analogy assumes a defined search area and suitable access. It does not promise that the item exists, that the search will be fast, or that an incomplete building map includes every relevant location.

Worked example

Consider a search tree whose root S has two children: A1 and G. Node G is a goal. The other branch continues forever: A1 has child A2, A2 has child A3, and so on. No A-node is a goal.

A depth-first tree search that selects the A branch first keeps descending indefinitely and never examines G. A solution exists only one edge from the root, but this procedure fails to find it. The example demonstrates incompleteness for that search setting.

Breadth-first search examines the root and then its finite first level. It reaches G without needing to finish the infinite branch. More generally, finite branching ensures that each level contains finitely many nodes, so a goal at finite depth is eventually reached.

Now suppose an external timer stops breadth-first search before G is examined. That interrupted run does not establish that no solution exists. The theoretical guarantee and the outcome of a resource-limited execution are different claims.

Illustrative case study

Fictional case: Ridgeway Planning tests a fast beam-search prototype. It keeps only a small number of promising candidates and discards the rest. On one test, it reports that no plan exists after its retained candidates fail.

A reviewer finds a valid plan in a discarded branch. The team changes the output to distinguish search failure from a proof of infeasibility and evaluates whether a complete fallback is needed for that workflow.

The fictional lesson is that an efficient heuristic can remain useful while lacking completeness. The product must describe the result it actually established rather than imply a stronger guarantee.

Common misconceptions and mistakes

Complete does not mean optimal. A method may reliably find some solution without finding the least-cost one.

Complete does not mean fast or memory-efficient. A guarantee of eventual discovery can coexist with impractical resource requirements.

Soundness and completeness are different. Deriving only justified conclusions does not ensure that every justified conclusion can be derived; deriving all consequences does not by itself exclude unjustified derivations.

Finally, completeness does not always guarantee termination when no solution or proof exists. Some procedures can eventually confirm positive cases while continuing indefinitely on negative ones. State whether the method is also a decision procedure for the problem class.

Business use

For businesses, completeness matters when missing a feasible plan or a logical consequence would affect the decision. Ask suppliers to identify the problem class and assumptions covered by their claim, including limits on graph structure, search pruning, and reasoning language.

Separate returned solutions, proven impossibility, and unresolved timeouts in reporting. Test representative difficult cases, but do not treat a successful test suite as a universal proof. Formal guarantees and practical evaluation provide different kinds of evidence and should be presented accordingly.

Check your understanding

A search discards a branch containing the only solution and never returns to it. Is it complete for that problem class?

Answer: No. It can fail to find an existing solution, which violates the search completeness requirement.

Related terms

Search algorithm
Entailment
Beam search
soundness
optimality
proof system
decision procedure
refutation completeness
termination

Learn next

Compare breadth-first and depth-first search on an infinite-branch example. Then study soundness and completeness in propositional inference, keeping the proof rules separate from the strategy used to explore possible proofs.

Depth First Search

Sources

Primary sources consulted: Poole and Mackworth, uninformed search guarantees, https://www.artint.info/3e/html/ArtInt3e.Ch3.S5.html ; Russell and Norvig, Logical Agents slides, https://aima.cs.berkeley.edu/slides-pdf/chapter07.pdf . The infinite-branch demonstration and fictional beam-search case are original. Search and inference senses are distinguished.

Previous: Completely randomized design Next: Completion