A computational problem refers to a task that can be formalized in terms of inputs, outputs, and a specific method or algorithm to transform the inputs into the outputs. In more technical terms, a computational problem consists of defining a set of instances, where each instance is associated with a specific input, and specifying the desired output for those inputs.
Articles by others on the same topic
A computational problem specifies what counts as a valid output for each permitted input. A binary relation can express this requirement: means that is a valid answer to . The computational problem is the specification; an algorithm is a proposed way to satisfy it.
For example, given an array and value , under the promise that occurs, a search problem can request any index with . Repeated values may give several valid outputs. The related decision problem only asks whether an occurrence exists and requires a yes-or-no answer. Stating the encoding, permitted instances and required answer prevents these tasks from being confused when comparing running time or verification costs.
