Definition
Problem
A problem is defined by a countably infinite set of possible instances (inputs) together with a question.
A problem is a computational task that requires a specific type of answer based on given inputs. These tasks are often categorised by the nature of their solution, such as decision problems requiring a “yes/no” answer, functional problems requiring a specific output, or optimisation problems seeking the best possible solution.
Infinite Instances
Why is a problem defined by an infinite number of instances?
- An algorithm must be applicable to an arbitrary instance of the problem statement.
- Assuming the number of instances is finite. Then, a possible solution would be to use a look-up table to index a solution for a given instance.
- An infinite number of instances guarantees that mathematical tools from Analysis can be used to describe the complexity can be used (e.g. Big O Notation).