A decision problem is a subset $D$ of a set of instances $A$, where generally $A$ is the set of finite bitstrings $\{0,1{\}}^{\ast }$.

In plain English, a decision problem is composed by a number of members of a collection, which generally share a common property.

A solution of the problem would consist in a procedure which given an instance $w$ of ${\Sigma }^{\ast }$ decides correctly in finite time whether $w$ belongs to $D$ or not. That is, a solution consists in a way of identifying the common trait shared by the members of $D$ which distinguish them from the rest of instances in $A$.

We say that a problem is decidable if there exists a solution which works for every instance.

We say that a decision problem is semidecidable if there is a procedure which identifies in finite time members of $D$, but fails to halt and reject instances which do not belong to $D$.

Decision problems can be classified according to their difficulty of solving in complexity classes, and are a central object of study in complexity theory.

Examples

Graph connectedness

Suppose we encode every possible finite graph, up to isomorphism, in the collection of finite bitstrings. Then we could define: $$CONNECTED=\{s\in \{0,1{\}}^{\ast }:s\text{represents a connected graph}\}$$ Which would be a decidable decision problem.

Tautology identification

Let $TAUTOLOGY$ be the collection of formulas of first order logic which are true for every interpretation. Then $TAUTOLOGY$ is a semidecidable decision problem, as if a formula is valid we can search for a proof, but otherwise we do not have an effective procedure to decide that a formula is not valid.