Suchprobleme

Suchprobleme, or search problems, are computational tasks where the input is given and the goal is to produce a witness that satisfies a specified relation. For many inputs there may be zero or more valid outputs; the objective is to compute one valid output when such outputs exist. This contrasts with decision problems, which ask only whether a witness exists, and with optimization problems, which seek the best output according to some criterion.

Formally, a search problem is defined by a relation R ⊆ Σ* × Γ*, where the domain Dom(R) = { x | ∃y (x,y) ∈ R }. For x ∈ Dom(R), a solution is any y with (x,y) ∈ R, and the set of solutions is S(x) = { y | (x,y) ∈ R }. In a total search problem, every x has at least one solution (S(x) ≠ ∅).

In complexity theory, Suchprobleme are studied through function classes such as FNP (the function analogue of NP) and TFNP (the total version, where every input has a solution). A central theme is how decision procedures can be used to obtain witnesses, via search-to-decision reductions or self-reducibility, although not all search problems admit efficient reductions.

Examples include SAT, where the task is to output a satisfying assignment for a given boolean formula; factoring, where one outputs a nontrivial factor of a composite number; and graph problems that require producing an actual path or structure, not merely a yes/no answer.

See also: NP, FP, FNP, TFNP, decision problems, optimization problems.