# 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

• Why is it called a de­ci­sion prob­lem? As a reader look­ing for an in­tu­itive un­der­stand­ing, that’s one of the first ques­tions I want an­swered.

Is it about de­cid­ing things? Is “Where should we go to eat tonight?” a de­ci­sion prob­lem? :-)