Computational problem #

A computational problem is (usually) specified as:

• a set of possible inputs, and
• the expected outputs (for these inputs).

Problem vs algorithm #

Example. Here is a well-known computational problem:

• Input: a sorted array $A$ of integers, an integer $a$
• Output: true if $a$ appears in $A$, false otherwise

There are (infinitely) many algorithms that solve this problem, some of which are more efficient than others.

Efficiency (a.k.a. computational cost) refers to the time and/or memory needed to execute an algorithm, expressed as a function of the size of the input (more on this later).

Example. Here is another problem that you may know:

• Input: an array of integers
• Output: an array with the same values, but sorted in ascending order

Example. And yet another:

• Input: a solvable grid of sudoku
• Output: the same grid, solved

Note. A problem specifies what a program should do, not how to do it. In other words, a computational problem is not an algorithm.

Example. The following is not a computational problem:

• Input: an array of integers.
• Algorithm: initialize a counter to $1$. Then iterate through the array, and:
  • increment the counter each time two consecutive numbers are encountered, or
  • reset the counter to $1$ otherwise.

To go further. A problem may be:

• undecidable; this means that no algorithm can exists that solves it for all inputs,

• decidable but intractable; this means that no algorithm can exist that solves it efficiently (where cost is once again measured as a function of the size of the input).