What is a problem?

In brief

Article summary

Algorithms are used to solve problems? But what do we mean by problems? Are there different kinds of problems?

Main takeaways

• Problems can be seen as functions from a domain to a codomain.

• An instance of a problem can have a solution, computed through an algorithm.

• A decision problem has a boolean codomain.

• A search problem is a problem for which there are several solutions.

Article contents

1 — A simple definition of a problem as a function

You have previously implemented algorithms as Python functions, but we can also consider that problems are defined by mathematical functions. Basically, we can say that a problem is defined by a function on a domain $I$ (for Input) and a codomain $S$ (for Solution).

An algorithm $A$ solves a problem $f : I \rightarrow S$, if for any $e \in I$ such that $f$ is defined on $e$, the algorithm $A$ applied to $e$ terminates in a finite amount of time and produces the result $f(e)$.

Each element $e$ defines an instance of the problem (we also say that $e$ parameterizes the problem) and $f(e)$ is the solution of the problem. The function $f$ is partial: there are elements $e \in I$ to which $f$ cannot be applied. This corresponds to instances of the problem that have no solution. Alternatively, we can consider $f$ as a total function by adding to $S$ a special element, let us say fail, which is returned if there is no solution.

A decision problem is simply a problem defined by a function $f : I \rightarrow \mathbb{B}$, where $\mathbb{B}$ is the set of booleans. The solution is binary, it is either true or false.

2 — Search problems

What about the case when there are several solutions? In that case, we say that the problem is a search problem. It is tempting to model such a problem with a function $f : I \rightarrow 2^S$, where $2^S$, also denoted $\mathcal{P}(S)$, is the power set of $S$. An element of $2^S$ is indeed a set of elements of $S$, that is a set of solutions. An empty set means that there is no solution. But we are not always interested in computing all the solutions. We can also imagine situations where not all the solutions can be computed in a finite amount of time!

A more general definition of a search problem relies on relations rather than functions. Here is such a definition:

A search problem with an input domain $I$ and a solution codomain $S$ is defined by a relation $R \subset I \times S$. An algorithm $A$ solves a search problem $R$ if, for any input $e \in I$, the algorithm $A$ applied to $e$ produces a solution $s$ such that $R(e, s)$ (or $(e, s) \in R$, a set of pairs), if such a solution exists.

Here, the algorithm produces a single solution. It is also possible to define an exhaustive search problem by using a function as discussed above.

3 — Optimization problem

An optimization problem is a refinement of a search problem $R$ where, instead of getting any solution, we want to get the best one. Here, best is defined by a cost function, i.e., a function $c: S \rightarrow \mathbb{R}^+$. Solving such a problem for an input $e$ produces a solution $s$ to the search problem such that $c(s)$ is minimal.

Any optimization problem can be turned into a decision problem by defining a bound and reformulating the problem as follows:

For a given input, is there a solution with a cost less than or equal to the bound?

To go further

Looks like this section is empty!

Anything you would have liked to see here? Let us know on the Discord server! Maybe we can add it quickly. Otherwise, it will help us improve the course for next year!

To go beyond

Looks like this section is empty!

Anything you would have liked to see here? Let us know on the Discord server! Maybe we can add it quickly. Otherwise, it will help us improve the course for next year!