Computational problem¶

A formally specified relation between encoded instances and acceptable solutions sought by an algorithm.

Version: v2 · 2026-09-19 · History
Domain-specific #: 3819
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Theoretical Computer Science → Computer Science & Software Engineering

Core Idea¶

A computational problem assigns each valid finite input representation a set of permitted outputs, with decision, search, counting, function, optimization, and promise forms distinguished by output and domain structure. An algorithm realizes a solution mapping under a model of computation, while complexity measures the resources needed as input size grows. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

Rules for Right Answers

A computational problem is a question with rules about which answers count as right. For example: 'Give me two numbers that add up to 10.' Lots of answers work, like 3 and 7, or 5 and 5. The problem is just the list of what's allowed — not the way you figure it out.

The Question Before the Program

A computational problem describes what a computer is supposed to do: for every possible input, it says which outputs count as correct. For example, "given a list, put it in order" is a problem, and any correctly sorted list is a right answer. The problem is not the same as the program that solves it; many different programs can solve the same problem. Some problems ask yes-or-no questions, some ask you to find something, some ask you to count, and some ask for the best choice.

Inputs Paired With Correct Outputs

A Computational problem assigns to each valid input, written in some finite form, a set of allowed outputs. The instances, the rule for which outputs are acceptable, how inputs are represented, and what counts as success are all fixed before any particular algorithm is chosen. Problems come in forms: decision problems (yes/no), search problems (find a solution), counting problems, function problems, optimization problems, and promise problems (where only certain inputs need to be handled). An algorithm is a way of producing correct outputs under some model of computation, and complexity measures how many resources that takes as input size grows. Keeping the problem separate from the algorithm is what lets us compare different solutions to the same problem.

A computational problem is a relation assigning to each valid finite input representation a set of permitted outputs. Its forms — decision, search, counting, function, optimization, and promise — are distinguished by the structure of the output and of the input domain. An algorithm realizes a solution mapping for the problem within a model of computation, and computational complexity measures the resources that mapping requires as input size grows. The problem's identity is fixed by four components specified independently of any particular algorithm: the instance set, the admissible-solution relation, the input representation, and the success condition. Because representation is part of the definition, the same abstract question encoded differently can have different complexity. Recognizing a computational problem means checking that these components are explicit; a piece of code, a benchmark, or an informal task description is not yet a problem in this sense.

Scope of Application¶

Computational problem belongs to theoretical computer science and is useful where the analyst can specify the typed theoretical computer science carrier, defining objects and relations, parameters, conventions, evidence, boundary cases and comparison targets, then evaluate the instance set, admissible-solution relation, representation, and success condition are explicitly fixed independently of any particular algorithm. The scope is broad within that domain but bounded by the need for the instance set, admissible-solution relation, representation, and success condition are explicitly fixed independently of any particular algorithm. The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the instance set, admissible-solution relation, representation, and success condition are explicitly fixed independently of any particular algorithm the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test. A bare label is insufficient because the name Computational problem can be used for a formal identity, an implementation, or a neighboring result unless carrier and convention are stated.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Computational problem. Computational problem compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed theoretical computer science carrier, defining objects and relations, parameters, conventions, evidence, boundary cases and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the instance set, admissible-solution relation, representation, and success condition are explicitly fixed independently of any particular algorithm independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of theoretical computer science because they reuse the typed theoretical computer science carrier, defining objects and relations, parameters, conventions, evidence, boundary cases and comparison targets, An algorithm realizes a solution mapping under a model of computation, while complexity measures the resources needed as input size grows., and type the carrier, state every parameter and convention in the definition, test that the instance set, admissible-solution relation, representation, and success condition are explicitly fixed independently of any particular algorithm, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Computational problem Domain-specific

Parents (1) — outgoing typed relations

Computational problem is a kind of Function (Mapping) Prime

What makes it its own entry: the domain-specific identity determined by the instance set, admissible-solution relation, representation, and success condition are explicitly fixed independently of any particular algorithm.

Children (18) — abstractions linked here by typed relations

3SUM Domain-specific is a kind of Computational problem

3SUM is a strict kind of Computational Problem: each finite input asks whether a three-element zero-sum witness exists.
Co-RE-complete Domain-specific is a kind of Computational problem

Co-RE-complete denotes a decision problem complete for co-RE, not the complexity class itself.
Dynamic Problem Domain-specific is a kind of Computational problem

Dynamic Problem is a domain-specific kind of computational problem under the frozen identity and differentia. Complete-catalog comparison found the corresponding live broader identity.
Element distinctness problem Domain-specific is a kind of Computational problem

Element distinctness problem is a strict kind of Computational problem: its frozen identity entails the parent's defining structure while adding domain-specific restrictions.
Envy minimization Domain-specific is a kind of Computational problem

Envy minimization specifies encoded allocation instances, feasible allocations, and the objective of minimizing declared envy.

▸ Show 13 more

Intersection Non-Emptiness Problem Domain-specific is a kind of Computational problem
Intersection Non-Emptiness Problem is a strict kind of Computational problem: it asks a finite encoded yes/no question about whether automata share an accepted string.
Metric k-center Domain-specific is a kind of Computational problem
Metric k-center maps metric instances to center selections minimizing the maximum assignment distance.
Mrs. Miniver's Problem Domain-specific is a kind of Computational problem
Mrs. Miniver's Problem is a strict kind of Computational problem: it specifies circle radii and asks for a placement satisfying one exact area equality.
NP-Equivalent Domain-specific is a kind of Computational problem
NP-equivalent tasks are computational problems.
Reconfiguration Domain-specific is a kind of Computational problem
A reconfiguration problem asks for reachability or connectivity between encoded solutions under allowed local moves.
Ring star problem Domain-specific is a kind of Computational problem
The ring-star problem specifies combinatorial network instances, feasible ring-star designs, and an optimization objective.
Search Problem Domain-specific is a kind of Computational problem
A search problem is a computational problem distinguished by its demand for an admissible output witness.
Set Cover Problem Domain-specific is a kind of Computational problem
Set cover is a strict Computational Problem: finite incidence input asks for a minimum complete cover or whether one exists within a bound.
Short Integer Solution Problem Domain-specific is a kind of Computational problem
SIS specifies encoded modular-matrix instances and a checkable nonzero short-kernel solution relation.
Smallest-Circle Problem Domain-specific is a kind of Computational problem
The smallest-circle problem maps a finite point set to a minimum-radius enclosing circle.
Stable Roommates Problem Domain-specific is a kind of Computational problem
Stable roommates is a strict Computational Problem: a finite preference instance asks whether a stable perfect pairing exists and requests a witness or impossibility result.
Stacker Crane Problem Domain-specific is a kind of Computational problem
The stacker crane problem is an encoded instance-to-feasible-tour optimization problem with a checkable solution criterion.
X + Y Sorting Domain-specific is a kind of Computational problem
X+Y Sorting is a Computational Problem asking for all Cartesian-product pairs to be ordered by coordinate sum while preserving duplicate sums.

Hierarchy path (1) — routes to 1 parentless root

Computational problem → is a kind of Function (Mapping)

Neighborhood in Abstraction Space¶

Computational problem sits in a crowded region of the domain-specific corpus (5^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Computational Complexity Classes & Hierarchies (30 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25