Decision problem

A de­ci­sion prob­lem is a sub­set \(D\) of a set of in­stances \(A\), where gen­er­ally \(A\) is the set of finite bit­strings \(\{0,1\}^*\).

In plain English, a de­ci­sion prob­lem is com­posed by a num­ber of mem­bers of a col­lec­tion, which gen­er­ally share a com­mon prop­erty.

In plainer English, a de­ci­sion prob­lem is a ques­tion of the form “does bit­string \(w\) have prop­erty \(p\), yes or no?”

Every ques­tion that fits the set form (is this string in the set?) can be re-ex­pressed as “does this bit­string have the prop­erty of be­ing in the set?” Every­thing that fits the prop­erty form can be re-ex­pressed in set form as well, be­cause a prop­erty im­plic­itly speci­fies a set of things that have the prop­erty. Thus, the two forms are equiv­a­lent.

It is called a de­ci­sion prob­lem be­cause we are try­ing to de­cide whether a given bit­string be­longs to the set or not.

A solu­tion of the prob­lem would con­sist in a pro­ce­dure which given an in­stance \(w\) of \(A\) de­cides cor­rectly in finite time whether \(w\) be­longs to \(D\) or not. That is, a solu­tion con­sists in a way of iden­ti­fy­ing the com­mon trait shared by the mem­bers of \(D\) which dis­t­in­guish them from the rest of in­stances in \(A\).

We say that a prob­lem is de­cid­able if there ex­ists a solu­tion which works for ev­ery in­stance. Triv­ially, finite de­ci­sion prob­lems are de­cid­able, since we can have a look-up list with ev­ery el­e­ment which we would con­sult ev­ery time we are given an in­stance to clas­sify. If the in­stance cor­re­sponds to an el­e­ment in the list, we ac­cept it, and oth­er­wise re­ject it.

We say that a de­ci­sion prob­lem is semide­cid­able if there is a pro­ce­dure which, in finite time, iden­ti­fies mem­bers of \(D\), but fails to halt and re­ject in­stances which do not be­long to \(D\).

De­ci­sion prob­lems can be clas­sified ac­cord­ing to their difficulty of solv­ing in com­plex­ity classes, and are a cen­tral ob­ject of study in com­plex­ity the­ory.

Examples

Graph connectedness

Sup­pose we en­code ev­ery pos­si­ble finite graph, up to iso­mor­phism, in the col­lec­tion of finite bit­strings. Then we could define:

$$ CONNECTED = \{s\in\{0,1\}^*:\text{$s$ represents a connected graph}\} $$
Which would be a de­cid­able de­ci­sion prob­lem.

Tau­tol­ogy identification

Let \(TAUTOLOGY\) be the col­lec­tion of for­mu­las of first or­der logic which are true for ev­ery in­ter­pre­ta­tion. Then \(TAUTOLOGY\) is a semide­cid­able de­ci­sion prob­lem, as if a for­mula is valid we can search for a proof, but oth­er­wise, we do not have an effec­tive pro­ce­dure to de­cide that a for­mula is not valid.

Primality

Let:

$$ PRIMES = \{ x\in \mathbb{N}:\text{$x$ is prime}\} $$
Then \(PRIMES\) is a de­cid­able de­ci­sion prob­lem.

We can al­ter­nately define

$$ PRIMES = \{s\in\{0,1\}^*:\text{$s$ represent a prime number in base $2$}\} $$
This illus­trates that we can spec­ify a par­tic­u­lar de­ci­sion prob­lem in differ­ent ways.

Parents:

  • Complexity theory

    Study of the com­pu­ta­tional re­sources needed to com­pute something