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 output witness, rather than just a yes/no answer about whether one exists. Formally, take encoded inputs \(x\), candidate outputs \(y\), and an admissibility relation \(R(x,y)\). On an input for which at least one \(y\) satisfies the relation, solving the task means producing some such \(y\). The associated decision question asks only whether \(\exists y\,R(x,y)\). The witness-production demand is the stable difference between the two.[1]
The task specification is independent of a chosen algorithm. Edmonds's maximum-weight matching task asks for a matching edge set; Shor's factorization task asks for a nontrivial divisor. Their graph and integer representations, validity predicates, and solvers differ, but each demands a concrete admissible output.[2][3] A no-witness input calls for an explicit convention if that case is admitted. Goldreich's basic formulation leaves it aside; a universal failure symbol is not part of the identity.[1]
Structural Signature¶
- Encoded instance family. State which finite representations count as inputs. A graph with edge weights and a binary integer have different carriers; without an input family there is no determinate task.[1][2][3]
- Admissibility relation. Define when a candidate \(y\) qualifies for \(x\). More than one witness may be valid. Removing or changing \(R\) changes the problem.[1]
- Witness output. Require an actual object satisfying \(R(x,y)\). Replacing it with a Boolean existence verdict changes the output form to a decision problem.[1]
- Production obligation on solvable inputs. A solution must return some admissible witness when the relation has one; checking a witness already supplied is a different operation. One solver may be replaced by another without changing this obligation.[1]
- Existence boundary. Separate inputs with a witness from those without one. Totality and a prescribed no-solution response are additional specifications, not silently assumed by the general search form.[1]
A particular solving algorithm is nonconstitutive. The matching and factoring papers study specific methods, but their output obligations can be stated without those methods.[2][3]
What It Is Not¶
A decision problem that answers “does a witness exist?” is a neighboring output form, not the search task that returns one. A verification procedure that receives a proposed witness and checks \(R(x,y)\) also does not by itself produce a witness. The live Search Algorithm concerns a procedure and its exploration behavior; the problem remains defined when a different kind of algorithm solves it.[1]
Neither polynomially bounded witnesses nor polynomial-time verification is required by this general identity. Those conditions characterize more specialized complexity settings in Goldreich's discussion. Nor does every search problem ask for an optimum: optimality belongs to the relation of a particular task, such as maximum-weight matching, not to witness production as such.[1][2]
Scope of Application¶
The scope is formal computational tasks with represented input and output objects and a declared validity relation. In maximum-weight matching, the input is a finite weighted graph, and a valid output is a pairwise nonincident edge set with maximum total weight for that input.[2] In nontrivial factor search, the input may be declared a composite integer \(n\), and an admissible output is a divisor \(d\) with \(1<d<n\) and \(d\mid n\). Shor's paper studies a quantum method for obtaining such a factor, not a quantum-only definition of the task.[3]
These examples do not imply that every search task is efficiently solvable or efficiently verifiable. A perfect-matching existence question is a useful derived near miss, but Edmonds's cited worked output is maximum-weight matching, not that exact yes/no question. A prime input has no nontrivial divisor under the stated factor relation; admitting it requires an explicit no-solution convention. In the matching example, an empty matching remains admissible when no edges are selected, so a maximum exists for a finite graph.[2][3]
Clarity¶
Write the task as input, admissible output, and required response. For a matching task, a number giving the best weight is not the same output as the matching edge set. For factorization, “composite” is a verdict, while a divisor is a witness. The associated decision language can help compare complexity, but does not replace the witness-output requirement.[1][2][3]
State the input promise and no-witness behavior rather than hiding them. Restricting factor inputs to composite integers gives a witness on every admitted input; admitting primes changes the existence domain. Calling every search problem total, or requiring one particular failure token on unsolvable inputs, would add conditions absent from the basic relation-defined form.[1]
Manages Complexity¶
The pair \(x,R\) compresses many task-specific details into a reusable question: which outputs count, and must one be produced? It lets an analyst keep the task separate from algorithms that try to solve it. Edmonds's graph method and Shor's quantum method can be discussed as different ways of meeting different output specifications, without making either method part of the general search definition.[1][2][3]
The compression does not erase the validity predicate. Matching requires a pairwise nonincident edge set with the specified maximum weight; factoring requires a proper divisor. The predicates may have different verification costs. A generic claim that every proposed witness is easy to check would import a restricted complexity assumption.[1][2][3]
Abstract Reasoning¶
Given \(R(x,y)\), define the associated decision question by \(L_R=\{x:\exists y\,R(x,y)\}\). A decision answer records membership in \(L_R\); a search answer supplies a qualifying \(y\). Knowing that \(x\in L_R\) does not itself hand over a witness. Reductions from decision to search need additional structure, such as the self-reducibility Goldreich treats conditionally.[1]
Now change one role at a time. Keep a weighted graph but request only its maximum weight: the requested output is a value, not the matching edge set in Edmonds's task. Keep a composite integer but replace Shor's order-finding solver with another factor-finding method: the search task remains the same. Admit prime inputs without changing \(R(n,d)\): the relation now has no witness for some inputs, and the response convention needs to be stated.[2][3]
Knowledge Transfer¶
The relation-and-output test transfers literally between graph and integer settings. In each, identify the encoded input, the predicate for an admissible output, and the demand to return a witness. Then preserve local facts: maximum total edge weight is a matching-specific predicate; divisibility is an arithmetic one. Neither predicate transfers to the other.[1][2][3]
The broader live Computational Problem entry already houses input representation, acceptable outputs, and success criteria for several output forms. The present entry adds witness production as a narrower task identity. In everyday language, “search” may mean information retrieval, physical exploration, or looking for a person. Without an encoded input/output relation and witness obligation, that vocabulary is only an analogy here.
Examples¶
Canonical: maximum-weight graph matching¶
Edmonds considers a finite graph \(G\) with stated edge weights. A matching \(M\) is a set of pairwise nonincident edges; the worked task returns one whose total weight is maximum. The paper provides an algorithm and a polyhedral analysis, but neither is a condition for recognizing the output task.[2]
Mapped back: encoded instance = weighted \(G\); admissibility = \(M\) is a matching of maximum total weight; witness = the edge set \(M\); production obligation = return one qualifying \(M\); existence boundary = a finite graph has at least an empty matching; optional solver = Edmonds's method. The optimum requirement is local to this instance relation.
Applied: nontrivial integer factor¶
Take a composite integer \(n\) in binary. The required output is a concrete \(d\) with \(1<d<n\) and \(d\mid n\). A yes/no compositeness statement would answer a related decision question but not deliver the divisor. Shor's order-finding construction is one way to find a factor under his algorithm's conditions; it is not built into the task definition.[3]
Mapped back: encoded instance = binary composite \(n\); admissibility = the proper-divisor relation; witness = \(d\); production obligation = return one qualifying divisor; existence boundary = a composite input has one, while a prime input would not under the same relation; optional solver = Shor's quantum method. The two examples share the task form, not their carriers or algorithms.
Structural Tensions¶
The original-source packet does not establish an intrinsic opposed-pressure tension required by all search problems. Finding versus deciding is a difference in requested output, not a trade-off inside one problem. Witness production versus verification is likewise a task distinction; efficiency of either operation depends on additional hypotheses. The diagnostic is to state exactly what the input supplies, what relation defines correctness, and whether the required response is a witness, a verdict, or another output.[1]
Structural–Framed Character¶
This entry is structural within theoretical computer science and formally framed. Its evaluative weight is low: a task does not become a search problem because its output is useful or its solver is fast. Human practice chooses representations, promises and problem statements; the witness relation then supplies a mathematical correctness test. Its institutional origin in complexity theory and algorithm design shapes the vocabulary and studied examples, not the relation-defined output obligation.
The words “input,” “output,” and “search” travel across fields, but their everyday use does not carry \(R(x,y)\) or the witness-production test. Recognition requires that formal task map. The existing Computational Problem parent is domain-specific; a putative cross-domain request-for-witness pattern would be a future-Prime question requiring independent noncomputational cases, with no such edge asserted here. Its character: a formal output-task specialization whose portability is real across computational carriers and bounded by its computational specification.
Structural Core vs. Domain Accent¶
The broader skeleton is the live Computational Problem identity: encoded instances, admissible outputs and a success condition independent of any one solver. The narrower core is a demand for an actual \(y\) satisfying \(R(x,y)\) on solvable inputs. Graph weights, edge sets, integer divisors, quantum order finding and matching algorithms are domain implementations or methods, not that core.[1][2][3]
Removing computational representation and the relation leaves a loose phrase such as “find something suitable.” That does not establish a ring-free or computation-free Prime called Search Problem. A more abstract cross-domain witness-request structure is only a future-Prime question to test with independent cases. The named child remains a theoretical-computer-science task type.
Instantiates / Related Primes¶
This entry is a kind of Computational problem.
The sole asserted strict edge is Search Problem → Computational Problem. Both mapped cases satisfy the parent input/output/success roles, and their witness obligation makes the child narrower. The live Search Algorithm is a procedure class, not a parent of the task. Integer Factorization and Maximum Matching name instances; FNP adds bounded and efficiently checkable witnesses under its own conventions.[1]
No direct edge to Function Mapping is added. The live Prime's identity is single-valued, while \(R\) may admit multiple witnesses; the existing Computational Problem entry's upward placement does not prove an additional child edge here. Relation is a formal ingredient but the nearer live computational parent carries the full task identity. Search and Retrieval has a query/location/relevance signature not required by these output tasks.
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.The live Computational Problem encompasses encoded inputs, permitted outputs, a success condition, and several output forms independent of a chosen algorithm. Every search problem specifies those roles through an instance family and a relation R(x,y). Its stable differentia is the demand to produce some valid y when one exists, not merely decide whether such a y exists or count witnesses. Maximum-weight matching and nontrivial integer factoring are unlike graph and arithmetic instances of this narrower task. The parent also includes decision-only and counting problems, so the child is strict. A solver or search algorithm is not the task's genus.
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¶
- An existence decision: returns a Boolean, not an admissible witness.[1]
- A search algorithm: is one procedure attempting to discharge a task, not its specification.
- A witness verifier: checks a supplied \(y\), without necessarily producing one.[1]
- A maximum-value-only request: is not the same requested output as an actual maximum-weight matching.[2]
- FNP, total search or a quantum factoring method: adds verification, existence or solver conditions not required of the general search-problem identity.[1][3]
References¶
[1] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u
[2] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n
[3] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m