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

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

In plainer English, a decision problem is a question of the form "does bitstring $w$ have property $p$ , yes or no?"

Every question that fits the set form (is this string in the set?) can be re-expressed as "does this bitstring have the property of being in the set?" Everything that fits the property form can be re-expressed in set form as well, because a property implicitly specifies a set of things that have the property. Thus, the two forms are equivalent.

It is called a decision problem because we are trying to decide whether a given bitstring belongs to the set or not.

A solution of the problem would consist in a procedure which given an instance $w$ of $A$ 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. Trivially, finite decision problems are decidable, since we can have a look-up list with every element which we would consult every time we are given an instance to classify. If the instance corresponds to an element in the list, we accept it, and otherwise reject it.

We say that a decision problem is semidecidable if there is a procedure which, in finite time, identifies 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: $C O N N E C T E D = {s \in {0, 1}^{*} : s represents a connected graph}$ Which would be a decidable decision problem.

Tautology identification

Let $T A U T O L O G Y$ be the collection of formulas of first_order_logic which are true for every interpretation. Then $T A U T O L O G Y$ 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.

Primality

Let: $P R I M E S = {x \in N : x is prime}$ Then $P R I M E S$ is a decidable decision problem.

We can alternately define $P R I M E S = {s \in {0, 1}^{*} : s represent a prime number in base 2}$ This illustrates that we can specify a particular decision problem in different ways.