Search Problem¶
A computational task that asks for an admissible output witness for each solvable encoded input, rather than only a verdict that one exists.
Core Idea¶
A search problem asks for an admissible output witness for an encoded input. Specify a relation \(R(x,y)\): \(x\) is an input, and \(y\) is an acceptable answer exactly when \(R(x,y)\) holds. For an input with at least one such \(y\), solving the task means producing one. The related decision question asks only whether any such \(y\) exists. It does not itself supply one.[^ref-27891b3e1d7b]
A search problem is a task specification, independent of a particular algorithm. A maximum-weight matching task requests an edge set; a factor-search task requests a divisor. Their carriers and solvers differ, but both demand a concrete witness.[ref-57138e7bdbb5][ref-73a701e356ce]
Scope of Application¶
This entry covers formal computational tasks with represented inputs, candidate outputs and a declared admissibility relation. Polynomially bounded or efficiently checkable witnesses are additional restrictions, not requirements for every search problem. An optimization task can qualify when the admissibility relation demands an optimal witness, as Edmonds's maximum-weight matching relation does.[ref-27891b3e1d7b][ref-57138e7bdbb5]
When an admitted input has no witness, the response convention must be stated. Goldreich's basic formulation leaves such inputs aside; it does not make one particular failure signal universal. Composite integers have nontrivial divisors, whereas primes have none under the same proper-divisor relation.[ref-27891b3e1d7b][ref-73a701e356ce]
Clarity¶
For any proposed task, write down input, valid output and required response. “A matching exists” is a Boolean statement; a list of matching edges is a witness. “The integer is composite” is a verdict; a proper divisor is a witness. A procedure that checks a supplied candidate does not by itself produce one.[ref-27891b3e1d7b][ref-57138e7bdbb5][^ref-73a701e356ce]
Keep the algorithm separate. Edmonds's matching method and Shor's quantum method are ways to solve particular tasks, not clauses in the general definition.[ref-57138e7bdbb5][ref-73a701e356ce]
Manages Complexity¶
The \(R(x,y)\) form lets graph and arithmetic tasks be compared through the same output question while keeping their validity predicates distinct. It also prevents a complexity claim about one solver or one restricted class from being imported into all search problems. Maximum edge weight belongs to the matching predicate; divisibility belongs to the factor predicate.[ref-27891b3e1d7b][ref-57138e7bdbb5][^ref-73a701e356ce]
Abstract Reasoning¶
The associated decision language is \(L_R=\{x:\exists y\,R(x,y)\}\). A decision answer says whether \(x\) belongs to this set; a search answer returns a qualifying \(y\). Deriving a witness from repeated decisions can require additional structure such as self-reducibility. Goldreich treats that as conditional, not automatic for every search task.[^ref-27891b3e1d7b]
Replacing Shor's solver while retaining the proper-divisor relation leaves the factor-search problem intact. Admitting prime inputs without changing that relation instead adds no-witness cases and requires an explicit convention.[^ref-73a701e356ce]
Knowledge Transfer¶
To recognize a new search problem, identify the encoded instance family, admissibility relation and demand to return a witness. This transfers literally from weighted graphs to integers. The broader live Computational Problem entry already covers encoded inputs, acceptable outputs and success criteria; witness production gives this child its narrower identity. An everyday use of “search” without this formal output obligation is only an analogy here.[^ref-27891b3e1d7b]
Example¶
Maximum-weight matching. Edmonds takes a finite weighted graph. An admissible witness is a set of pairwise nonincident edges whose total weight is maximum; the task returns the edge set, not just the optimal value. Thus the graph is the input, the matching-and-weight condition is \(R\), and the edge set is the required output. Edmonds's algorithm is one optional solver.[^ref-57138e7bdbb5]
Nontrivial factor. For a composite integer \(n\), a witness is an integer \(d\) with \(1<d<n\) and \(d\mid n\). The required response is \(d\), not merely “composite.” Shor develops a quantum method for this output task, but the witness relation does not require his method.[^ref-73a701e356ce]
Relationships to Other Abstractions¶
Current abstraction Search Problem Domain-specific
Parents (1) — more general patterns this builds on
-
Search Problem is a kind of Computational problem Domain-specific
A search problem is a computational problem distinguished by its demand for an admissible output witness.
Hierarchy path (1) — routes to 1 parentless root
- Search Problem → Computational problem → Function (Mapping)
Neighborhood in Abstraction Space¶
Search Problem sits in a sparse region of the domain-specific corpus (84th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Combinatorial Set Systems & Counting (9 abstractions)
Nearest neighbors
- Clique graph — 0.83
- Tractable Problem — 0.82
- Pseudo-polynomial transformation — 0.81
- Intersection graph — 0.81
- Nonelementary Problem — 0.81
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
A decision-only existence question, a verifier of a supplied candidate and an algorithm that explores possible outputs are not the same as the witness-production task. Nor must a general search problem be total, efficiently solvable, efficiently verifiable, or an optimization problem. The strict parent is Computational Problem; particular matching and factoring tasks are instances, not broader genera.[ref-27891b3e1d7b][ref-57138e7bdbb5][^ref-73a701e356ce]
References¶
[^ref-57138e7bdbb5]: Jack Edmonds, “Maximum Matching and a Polyhedron With 0,1-Vertices”, Journal of Research of the National Bureau of Standards B 69B (1965), 125–130, abstract and §§1–2, printed pp.125–126 (PDF pp.1–2). Original full paper inspected. Defines matching as pairwise nonincident edges and works the maximum-weight output problem; its particular algorithm is not the general search definition.
[^ref-27891b3e1d7b]: Oded Goldreich, Introduction to Complexity Theory, 1999 draft, Lecture 1 §1.3, printed pp.3–4 (PDF pp.25–26, zero-index pp.24–25). Original full author text inspected. Defines relation-based search, distinguishes the associated decision language, and scopes polynomial balance, recognition and self-reducibility to further conditions. Its basic formulation ignores inputs with no witness.
[^ref-73a701e356ce]: Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, author paper, arXiv quant-ph/9508027v2 (1996), §5 “Prime factorization,” PDF pp.15–16 (zero-index pp.14–15). Original full paper inspected. The section seeks a nontrivial factor and develops a quantum order-finding solver with stated success conditions; this entry uses the factor-output task, not a universal complexity claim.