Recognition problem

From Encyclopedia of Mathematics
Jump to: navigation, search

An algorithmic problem in which, given a set $A$, it is required to construct an algorithm recognizing $A$ with respect to another set $B$ containing $A$ ($A\subseteq B$), that is, an algorithm $\mathfrak A$ which is applicable to any element of $B$, and such that $\mathfrak A(x)=1$ if $x\in A$ and $\mathfrak A(x)=0$ if $x\in B\setminus A$. An important class of algorithmic problems is constituted by the recognition problems for formal theories, that is, the recognition problem for the set of all provable formulas in a theory (the set $A$) with respect to the set of all formulas in the theory (the set $B$).

The term "recognition problem" should be distinguished from the term "decidability problem", which is the question whether some mathematical problem or other (for example, an algorithmic problem) is solvable (cf. Decision problem).

How to Cite This Entry:
Recognition problem. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article