On specifying a problem

Before analysing an algorithm we have to fix what counts as a valid input, what the output should be, and precisely when an output is correct. Until then, “find the shortest path” is a wish, not a problem.

The correctness relation

Let $I$ be the set of inputs and $O$ the set of outputs. A computational problem is a relation $R \subseteq I \times O$: the pair $(x, y)$ belongs to $R$ exactly when $y$ is an acceptable answer for $x$. Stating it as a relation keeps the door open for inputs that admit several correct answers.

An algorithm $A$ solves the problem when, for every $x \in I$, it halts and $R(x, A(x))$ holds. Termination and correctness are separate obligations — neither implies the other.