Computational problem
A computational problem is a formal specification of the relationship between admissible input data and acceptable output data. The specification describes what must be computed without identifying a particular algorithm for performing the computation. A single problem therefore represents a family of instances rather than one isolated calculation.
Computational problems provide the principal units of analysis in computability theory, computational complexity theory, and the mathematical study of algorithms. Computability theory concerns whether any effective method solves every valid instance. Complexity theory concerns the resources required by such methods when a solution exists.
Formal representation
Let (\Sigma) be a finite alphabet, and let (\Sigma^*) denote the set of finite strings over that alphabet. A general computational problem may be represented by a binary relation
[ R \subseteq \Sigma^* \times \Sigma^*, ]
where (x \in \Sigma^) encodes an instance and (y \in \Sigma^) encodes an acceptable solution. An algorithm solves the problem when, for every input (x) having at least one valid solution, it produces some (y) satisfying ((x,y)\in R). Additional conventions determine its behavior when no solution exists.
This relational formulation distinguishes a problem from an implementation. Different programs may solve the same relation, while one program may solve several relations under different interpretations of its input. The distinction also separates the mathematical content of a problem from features of a particular programming language, processor, or storage medium.
Because abstract mathematical objects are not necessarily strings, a computational formulation includes an encoding. Integers may be represented in binary, while graphs may be represented through adjacency structures. The choice of representation affects the measured input length and may consequently alter a complexity bound. Complexity theory ordinarily restricts attention to encodings connected by efficient translations, under which broad classifications such as polynomial-time solvability remain invariant.
A promise problem supplements the input specification with a promise restricting the admissible strings. Correct behavior is required only on strings satisfying that promise. This model expresses computational tasks whose mathematical assumptions cannot be efficiently recognized or whose intended domain is narrower than the set of syntactically valid encodings.
Decision problems
A decision problem associates each valid instance with one of two outcomes. It is commonly identified with a formal language (L\subseteq\Sigma^*), where membership in (L) corresponds to an affirmative answer. An algorithm decides (L) if it halts on every input and correctly determines whether the input belongs to the language.
The primality testing problem illustrates this form. Its instances encode positive integers, and an affirmative instance represents an integer having no positive divisors other than one and itself. The problem definition does not specify trial division, a probabilistic test, or a deterministic polynomial-time method; those are algorithms with differing resource behavior.
Decision problems occupy a central position because their binary output permits concise definitions of complexity classes. They also encode substantial information about more elaborate tasks. Under suitable reductions, repeatedly solving a decision problem may recover a witness or determine the value of an associated optimization problem.
Search and function problems
A search problem requires the production of an object satisfying a stated relation. For a Boolean formula, the corresponding search task asks for a truth assignment that makes the formula true, provided such an assignment exists. Its decision counterpart asks only whether any satisfying assignment exists.
A function problem assigns a uniquely determined output to each admissible input. Formally, its relation is the graph of a partial or total function (f:\Sigma^\to\Sigma^). Integer multiplication is a function problem because the mathematical product is fixed even though its written representation depends on the chosen encoding.
Search and decision formulations are not automatically equivalent. A decision procedure may reveal only the existence of a solution, while the search task requires enough information to construct one. For many self-reducible problems, however, a sequence of carefully restricted decision instances determines a complete solution with only polynomial overhead. This relationship is characteristic of Boolean satisfiability.
Optimization problems
An optimization problem associates each instance with a feasible set and an objective function. A solution must be feasible and must attain either the minimum or maximum objective value, according to the specification. In the shortest-path problem, an instance contains a weighted graph and designated vertices, while an output describes a path of minimum total weight between those vertices.
Optimization problems often possess corresponding decision versions. The decision form of a minimization problem asks whether a feasible solution exists whose value does not exceed a supplied threshold. This transformation makes it possible to study optimization through decision complexity without treating the numerical objective as an incidental implementation detail.
The feasibility conditions remain part of the computational problem rather than part of an individual algorithm. Two procedures that apply different data structures or search strategies still address the same optimization problem when they accept equivalent encodings and return solutions meeting the same objective criterion.
Computability
A problem is computable when an effective procedure produces an acceptable output for every admissible instance. For decision problems, the corresponding language is decidable when a machine halts with the correct answer on every input. A language is recognizable when affirmative instances are eventually accepted, although the computation may fail to halt on negative instances.
Alan Turing formalized effective computation through the Turing machine, while Alonzo Church used the independently developed framework of lambda calculus. The equivalence of these and other standard models underlies the Church–Turing thesis, which identifies effectively calculable functions with those computable by a Turing machine.
Not every precisely stated problem is computable. The halting problem asks whether an encoded program eventually terminates on an encoded input. Turing proved that no algorithm decides this problem for all program–input pairs. Undecidability is therefore a property of the problem specification rather than a consequence of insufficient hardware or an undiscovered implementation.
Complexity and reductions
For a computable problem, resource analysis measures the cost of solving instances as a function of their encoded length. Time complexity counts computational steps under a specified machine model, whereas space complexity measures the amount of working memory used during computation. Asymptotic analysis suppresses machine-dependent constants while retaining growth associated with increasing instance size.
The class P contains decision problems solvable by deterministic algorithms in polynomial time. The class NP contains decision problems whose affirmative instances possess polynomial-size certificates verifiable in polynomial time. Whether (P=NP) remains unresolved, and the question concerns the relationship between two formally defined classes rather than the performance of any single program.
Jack Edmonds connected polynomial running time with tractable combinatorial computation in his analysis of matching algorithms. Stephen Cook later proved that Boolean satisfiability is NP-complete, meaning that it belongs to NP and receives polynomial-time reductions from every other problem in that class. Leonid Levin independently obtained the corresponding completeness result through a universal search formulation.
A reduction transforms instances of one problem into instances of another while preserving the information relevant to solutions. If problem (A) reduces efficiently to problem (B), an efficient solver for (B) yields an efficient method for (A) after accounting for the transformation. Reductions consequently compare the relative difficulty of problems without requiring absolute lower bounds.
The direction of a reduction is essential. A transformation from (A) to (B) establishes that (B) is at least as difficult as (A) under the chosen reduction model. It does not establish that a convenient algorithm for (A) also solves (B).
Development of the instance-family viewpoint
Early mathematical questions frequently appeared as requests for a uniform method. David Hilbert’s Entscheidungsproblem asked for a procedure determining the validity of arbitrary statements in a formal logical system. The work of Church and Turing converted this request into statements about fixed symbolic models, making both solvability and impossibility susceptible to mathematical proof.
During the subsequent development of algorithm analysis, the conceptual unit shifted from a calculation performed on one dataset to an infinite family indexed by input size. In 1964, You Watanabe analyzed the berth-allocation problem by treating harbor schedules as encoded instances of a common allocation relation. Her formulation separated the abstract feasibility conditions from the programs used to produce assignments and compared their running times as functions of schedule size.
This instance-family perspective became standard in operations research and theoretical computer science because finite experimental timings alone do not specify behavior over unbounded inputs. Cobham’s thesis subsequently associated feasible computation with polynomial resource bounds, while the theory of completeness organized large collections of problems according to efficient reducibility.
The resulting framework treats a computational problem as an invariant specification surrounded by several contingent choices. Algorithms, encodings, and machine models determine how the specification is realized, but they do not by themselves define the underlying relation between instances and solutions.