Algorithm¶
Core Idea¶
An algorithm is a finite, definite, effective procedure for transforming inputs into outputs by a sequence of prescribed steps. The essential commitment is to procedure: not just what the output should be (that is the function), but the ordered, mechanically-executable way of producing it. Every algorithm specifies (1) its admissible inputs, (2) a finite sequence of unambiguous steps, (3) a termination condition that it is guaranteed (or expected) to reach, and (4) a result it produces at termination. The classical constraints — finiteness, definiteness, effectiveness — together ensure that the procedure can be executed without appeal to intelligence or judgment.
How would you explain it like I'm…
Step-by-Step Recipe
Recipe of Exact Steps
Step-by-Step Procedure
Structural Signature¶
- The well-defined finite computational procedure (Knuth, 1997) [1]
- The input-to-output deterministic-or-randomized mapping (Motwani & Raghavan, 1995) [2]
- The correctness-and-termination invariants (Hoare, 1969) [3]
- The time-and-space resource bounds (Hartmanis & Stearns, 1965) [4]
- The abstract-machine-execution model independence (Turing, 1936) [5]
- The constructive-versus-existential proof distinction (Bishop, 1967) [6]
What It Is Not¶
- Not a function. A function is the mapping from inputs to outputs; the algorithm is a procedure that computes it. Many algorithms can compute the same function; some functions (the halting function, among others) have no algorithm at all.
- Not a heuristic. A heuristic is a procedure without a guaranteed correctness or termination claim; an algorithm, in the formal sense, comes with such claims. Many practical "algorithms" are heuristics with good empirical behavior.
- Not a program. A program is an algorithm written in a particular language on a particular machine; the algorithm is the procedure independent of how it is expressed or where it runs. The same algorithm has many programs.
- Not a policy. A policy chooses actions in a system over time; an algorithm, in the classical sense, computes an output from an input. Reinforcement-learning and control "policies" are closely related but extend beyond the input-output frame.
- Not a recipe in the colloquial sense. A cooking recipe involves steps whose execution requires judgment ("cook until golden"); a strict algorithm must reduce such steps to mechanically-checkable conditions.
- Common misclassification. Describing a vague workflow or set of guidelines as an algorithm without the definiteness and effectiveness constraints — and then being surprised that different executors produce different outputs from the same input.
Broad Use¶
- Computer science and mathematics
- Sorting, searching, optimization, graph algorithms, numerical methods, cryptographic algorithms.
- Operations research and logistics
- Routing, scheduling, assignment, inventory optimization.
- Medicine
- Diagnostic protocols, treatment decision trees, triage rules.
- Law and policy
- Sentencing guidelines, benefits-eligibility computations, risk-scoring algorithms (with attendant fairness concerns).
- Cooking, manufacturing, construction
- Recipes, assembly procedures, step-by-step build plans.
- Everyday reasoning
- Any "how-to" that reduces a goal to a sequence of executable steps.
Clarity¶
Algorithm clarifies by separating what is computed (the function) from how it is computed (the procedure), and by forcing each step to be mechanically executable. Vague "strategies" resolve into precise steps or reveal themselves to be insufficiently specified. The clarifying force is to make executability checkable — to turn a plan into something a disinterested executor (or a machine) can follow without interpretation.
Manages Complexity¶
- Reduces problem-solving to a finite recipe: once an algorithm exists, solving any instance of the problem requires only executing the recipe, not re-inventing the solution.
- Enables cost analysis: time and space complexity can be reasoned about from the step structure alone, giving meaningful predictions before any execution.
- Supports composition: algorithms call other algorithms as subroutines, letting large problems be decomposed into smaller algorithmic pieces.
- Separates correctness from efficiency: whether the output is right, and whether it is produced affordably, are questions that can be asked and answered independently.
- Makes human intuition transferable: once an expert's diagnostic procedure is algorithmized, it can be executed by others (or machines) without the expert.
Abstract Reasoning¶
Algorithm trains a reasoner to ask:
- What function is this algorithm supposed to compute? Does every instance of the described procedure actually compute it?
- Is the procedure finite, definite, and effective at every step?
- Does it terminate? On every input, or only on some? If only on some, what happens on inputs outside that set?
- What is the cost (time, space, communication) as a function of input size, and how does it scale?
- Is the algorithm deterministic, randomized, or approximate? What guarantees correspond to each regime?
- Is there a simpler algorithm with the same guarantees, or a faster one with different guarantees (approximate, probabilistic)?
Knowledge Transfer¶
Role mappings across domains:
- Algorithm ↔ procedure / protocol / recipe / workflow / decision tree / drill
- Input ↔ given data / initial state / query / problem instance
- Step ↔ instruction / action / substep / decision point
- State ↔ working memory / partial result / intermediate value / progress
- Termination condition ↔ halt test / completion criterion / stopping rule
- Output ↔ answer / decision / produced artifact / result
- Complexity ↔ running time / resources required / labor hours / lead time
- Subroutine ↔ sub-procedure / module / step sequence invoked within the larger procedure
A software engineer implementing a sort, a physician following a diagnostic protocol, and a pilot running a preflight checklist are doing the same structural work: specify the input, execute a finite definite sequence of steps, reach a termination condition, and produce a well-defined output. The same properties — termination, correctness under well-formed inputs, behavior under ill-formed inputs, predictable cost — are the diagnostic framework across all three settings, even though the steps themselves belong to wildly different domains.
Examples¶
Formal/abstract¶
Cormen-Leiserson-Rivest-Stein (2009) defined an algorithm as any well-defined computational procedure that takes input and produces output[7]. Dijkstra's (1959) shortest-path algorithm exemplifies this: given a graph with non-negative edge weights and a source vertex, produce the shortest path to every other vertex. The input class is precisely specified (graphs with non-negative weights); the steps are definite (maintain a frontier, extract minimum-distance vertex, relax edges); termination is guaranteed in V iterations; the output satisfies a correctness claim (distances are globally optimal). Every element of algorithmic structure is present, and the algorithm is independent of any particular programming language or machine architecture[8].
Mapped back: This instantiates the structural signature directly — finite steps, definite execution, guaranteed termination, deterministic correctness claim, machine-independent description.
Applied/industry¶
An airline's preflight checklist embodies algorithmic structure in a non-computational domain, a parallel Gawande (2009) develops at length in The Checklist Manifesto. The input is a specific aircraft in a given configuration; the steps are definite enough that two pilots executing them independently produce the same final state; termination is reached when the checklist is complete; the output is a verified ready-for-departure configuration. The same properties apply: correctness (all safety-critical items verified), termination (finite procedure), and cost analysis (time-to-complete). The structural kinship with Dijkstra is precise— same diagnostic questions, same failure modes — even though one acts on graphs and the other on aircraft[9].
Mapped back: This shows the same structural commitments (input, finite steps, definite execution, guaranteed termination, measurable correctness) translate across domains, demonstrating algorithm's role as a universal abstraction of procedure.
Structural Tensions¶
-
T1: Correctness vs Efficiency. A procedure can be correct but expensive, efficient but wrong, or correct in typical cases but pathological in adversarial ones. This trade-off is governed by the problem's intrinsic hardness and the algorithm designer's choices about cost allocation, as Aho, Hopcroft, and Ullman (1974) develop in their classical analysis of algorithm design. A common failure is optimizing for speed while discarding the correctness guarantees an algorithm once provided, without explicit acknowledgment[10].
-
T2: Algorithm vs Heuristic. Classical algorithms come with correctness and termination guarantees; heuristics drop those for simplicity or empirical performance, a distinction Pearl (1984) treats systematically in his foundational study of heuristic search. Many systems use heuristics under the "algorithm" label, inheriting neither the rigor of the former nor the honesty of the latter. A common failure is treating a heuristic as a correct algorithm, assuming guarantees it does not have, then being surprised by edge-case failures[11].
-
T3: Specification vs Implementation. An algorithm is a procedure described in some notation; an implementation is that procedure on a real machine with finite precision, memory, and time. Properties of the implementation can diverge from the abstract algorithm (numerical instability, overflows, concurrency bugs, pathological inputs for the specific machine), a class of risks Goldberg (1991) catalogs in his canonical survey of floating-point arithmetic. A common failure is reasoning about the abstract algorithm while the implementation silently violates its assumptions[12].
-
T4: Determinism vs Randomization/Approximation. Deterministic algorithms give the same output on the same input with worst-case guarantees. Randomized and approximate algorithms trade those for simpler or faster procedures with weaker (probabilistic or approximation-ratio) guarantees, a regime Karp (1991) surveys in his treatment of randomized complexity classes. A common failure is confusing the guarantees of different algorithm classes— treating "expected" performance as worst-case or vice versa[13].
-
T5: Termination Proof vs Practice. Proving that an algorithm terminates (reaches a halt condition on every admissible input) is theoretically necessary and practically essential. However, the proof can be subtle — it requires a well-founded measure and disciplined treatment of boundary cases, a methodology Floyd (1967) introduced through inductive assertions and well-founded ordering. A common failure is assuming termination without formal verification, leading to infinite loops on certain inputs[14].
-
T6: Abstraction vs Overhead. Expressing a procedure as an algorithm requires abstracting away implementation details, which clarifies the essential logic but can hide performance characteristics critical to practice. A procedure can be algorithmically elegant yet computationally infeasible on actual hardware, a tension Sedgewick and Wayne (2011) address by pairing every algorithm with empirical performance measurement. A common failure is prioritizing algorithmic clarity over practical executability[15].
Structural–Framed Character¶
Algorithm sits at the structural end of the structural–framed spectrum: it is a pure relational pattern that applies unchanged across domains, and its meaning does not lean on any one field's vocabulary or assumptions.
Though closely associated with computer science, the prime names a domain-neutral object — a finite, definite, effective procedure that transforms admissible inputs into outputs through unambiguous ordered steps with a termination condition. That same definition fits a cooking recipe, a long-division method, or a bureaucratic procedure equally well. It carries no normative weight, and its conditions of correctness, termination, and complexity are purely formal, owing nothing to human institutions. Applying the concept means recognizing a procedure that is already specifiable in itself. On every diagnostic, it reads structural.
Substrate Independence¶
Algorithm is about as substrate-independent as a prime can be — composite 5 / 5 on the substrate-independence scale. A finite, definite, effective procedure is a medium-neutral object, and the same diagnostic questions — does it terminate, is it correct, what does it cost — apply equally to computation, mathematics, medicine, law, manufacturing, and aviation checklists. Its cross-domain reach is real and documented, from Gawande's surgical checklists to sentencing and triage protocols. The one wrinkle is that demonstrated load sits slightly more in formal and procedural fields than a perfect 5 would, so transfer evidence reads a touch lower even as the composite stays universal.
- Composite substrate independence — 5 / 5
- Domain breadth — 5 / 5
- Structural abstraction — 5 / 5
- Transfer evidence — 4 / 5
Relationships to Other Abstractions¶
Current abstraction Algorithm Prime
Parents (1) — outgoing typed relations
-
Algorithm presupposes, conditional Function (Mapping) Prime
An algorithm presupposes Function Mapping when its complete declared inputs determine one terminating output; unmodeled random choices or partial behavior fall outside this condition.For an algorithm whose fully declared input includes all state and choices relevant to the result, and whose execution terminates with one result for each admitted input, the procedure realizes a deterministic single-valued mapping. Function Mapping captures that extensional result, while Algorithm adds an effective procedure and resource behavior. An algorithm that samples fresh choices over a fixed problem input, depends on undeclared state, or can diverge on a declared input does not meet this condition until its input, domain, and termination contract are explicitly refined. This is a conditional relation, not a strict claim about every Algorithm instance.
Condition / exception The procedure's extensional result is total and single-valued on a fully declared input domain; any random choices or relevant environment state are fixed as explicit inputs, and every admitted execution in that domain terminates with one result.
Children (80) — abstractions linked here by typed relations
-
AKS primality test Domain-specific is a kind of Algorithm
AKS is a deterministic finite procedure for deciding primality.AKS is a deterministic finite procedure for deciding primality.
-
Alternating-Direction Implicit Method Domain-specific is a kind of Algorithm
Alternating implicit solves form a definite numerical procedure for a specified target.Every ADI method specifies input numerical data, an ordered sequence of alternating implicit subsolves, and an approximate output or iteration criterion. That entails live Algorithm's stepwise problem-solving procedure; the child adds split numerical operators, implicit equations and variant-specific convergence conditions.
-
Bisection Method Domain-specific is a kind of Algorithm
Algorithm is the strict parent because bisection prescribes finite executable steps, maintains a correctness invariant, terminates under a tolerance rule, and has an explicit evaluation bound.The domain-specific residual is the continuous sign-bracketed root problem and its certified nested enclosure.
- Block walking Domain-specific is a kind of Algorithm
Block walking is a domain-specific kind of Algorithm: Block walking is a combinatorial proof technique that traverses structured blocks of a configuration according to local transition rules so a global counting, ordering, or existence result follows from the walk.The parent supplies the necessary broader identity—Step-by-step problem-solving procedure.—while the candidate adds the source-domain carrier, recognition rule, and failure conditions. The defining source account begins: Block walking is a combinatorial method that represents restricted paths on a rectangular street grid as sequences of elementary moves.
- Bruun's FFT algorithm Domain-specific is a kind of Algorithm
It is a finite computational procedure for the DFT.What makes it its own entry: a real-coefficient polynomial-factorization route to FFT computation with characteristic accuracy and implementation tradeoffs.
- Chang–Roberts Algorithm Domain-specific is a kind of Algorithm
**`prime:algorithm`** is the broader abstraction this entry instantiates: Chang–Roberts is a finite rule system mapping admissible distributed executions to a selected leader.**Selection** is conceptually related because the maximal UID is chosen, and **Suppression** describes message extinction. Neither supplies the procedural and communication structure, so no additional parent is proposed.
- Constant false alarm rate Domain-specific is a kind of Algorithm
CFAR is a strict Algorithm: finite reference-window inputs are transformed by an adaptive estimator and threshold rule into a terminating target/no-target decision.A CFAR variant specifies finite inputs, estimator and threshold mapping, decision output, calibrated error behavior, bounded termination, and explicit resource costs independent of one hardware implementation.
- Dadda multiplier Domain-specific is a kind of Algorithm
Dadda multiplier is a domain-specific kind of Algorithm: Hardware multiplier design.The parent supplies the necessary broader identity—Step-by-step problem-solving procedure.—while the candidate adds the source-domain carrier, recognition rule, and failure conditions. The defining source account begins: A Dadda multiplier is a combinational hardware architecture for binary multiplication that compresses columns of partial-product bits through a deliberately staged adder tree.
- Davis–Putnam Algorithm Domain-specific is a kind of Algorithm
**`prime:algorithm`** is the broader abstraction this entry instantiates.Davis–Putnam is a finite, definite, effective procedure from CNF inputs to a SAT/UNSAT result, with correctness and termination obligations. It specializes Algorithm by fixing its representations, steps, invariant, and terminal certificates. **`domain_specific:equisatisfiability`** is a constitutive invariant and close neighbor, not the genus: the relation can hold between formulas without any Davis–Putnam procedure. **`prime:deductive_reasoning`** supplies resolution's truth-preserving inferential background but is too broad to classify the algorithm.
- DIIS Domain-specific is a kind of Algorithm
DIIS is an iterative residual-minimizing procedure for extrapolating improved solutions.DIIS is an iterative residual-minimizing procedure for extrapolating improved solutions.
- Direct Linear Transformation Domain-specific is a kind of Algorithm
**`prime:algorithm`** is the broader abstraction this entry instantiates.DLT is a finite, definite procedure mapping point correspondences to a projective model estimate through normalization, design-matrix construction, SVD, denormalization, and optional constraint restoration. `prime:transformation` describes the model being estimated, not the procedure itself. `prime:linearity` describes why the relaxed coefficient solve is tractable. The accepted `domain_specific:geometric_transformation` node requires invertibility and is therefore not a valid universal parent for camera-projection DLT.
- Dispersive Flies Optimisation Domain-specific is a kind of Algorithm
DFO is a finite randomized input-to-output procedure with prescribed update steps and a stopping budget.Given bounds, objective, population, disturbance threshold and an evaluation budget, DFO prescribes effective fitness, selection, coordinate-proposal and replacement steps and returns a best found candidate when its budget ends. Random draws make its output stochastic, but the finite, executable procedure satisfies Algorithm's genus without promising the global optimum.
- Division Algorithm Domain-specific is a kind of Algorithm
Division Algorithm is a strict specialization of `prime:algorithm`: it is a terminating, unambiguous procedure with defined inputs and outputs, but adds the arithmetic quotient–remainder contract.That is the broader abstraction this entry instantiates. `prime:partition` is declined because the arithmetic residual is not an arbitrary division into parts. `prime:approximation` is used by reciprocal methods but is not invariant across repeated-subtraction or exact digit methods. `domain_specific:sorting_algorithm` is a sibling specialization with different postconditions.
- Enumeration Algorithm Domain-specific is a kind of Algorithm
**`algorithm` — confirmed strict parent.** Every enumeration algorithm is an algorithm: it accepts an encoded input, executes definite effective steps, preserves correctness invariants, and has explicit termination and resource semantics.Enumeration adds a set-valued output contract, uniqueness and coverage obligations, and output-sensitive scheduling. The proposed prose edge is **subsumption, strict**: `enumeration_algorithm` is a kind of `algorithm`, while many algorithms decide, optimize, count, transform, or find one witness without enumerating.
- Euler Method Domain-specific is a kind of Algorithm
**`prime:algorithm`** is the broader abstraction this entry instantiates.Euler Method is a finite executable recurrence with declared inputs and stepwise output. The parent does not supply the ODE substrate, tangent update, order, or stability function. `prime:approximation` captures the good-enough representation but not the procedure. `domain_specific:differential_equation` is the object being solved, not the method’s taxonomic genus. `prime:iteration` describes repeated application but would omit numerical accuracy and the derivative binding.
- Evolutionary Algorithm Domain-specific is a kind of Algorithm
**`prime:algorithm`** is the broader abstraction this entry instantiates.An EA is an executable problem-solving procedure with defined state and repeated operations. The child adds a population, evaluation-guided selection, heritable variation, and replacement. `prime:natural_selection` supplies the variation–selection–retention engine and is a strong related abstraction, but it is substrate-neutral and does not entail engineered representation or termination. `prime:optimization` names a common purpose, yet some EAs pursue novelty or diverse repertoires. `prime:variation_strategies` supplies deliberate generation of alternatives but not differential population replacement.
- Exponential Integrator Domain-specific is a kind of Algorithm
Exponential Integrator instantiates **Algorithm**: it is a terminating computational procedure for advancing a numerical state, and `prime:algorithm` is the broader abstraction this entry instantiates.It also instantiates **Approximation**, because the residual integral and matrix-function actions are numerically approximated, and **Iteration**, because one-step maps are repeatedly applied. Those latter relations are explanatory rather than proposed direct parents; Algorithm already captures the closest taxonomic role, while extra edges would add little placement information. Decomposition is relevant to the choice $f(u)=Lu+N(u)$, but the candidate is not a kind of decomposition. Differential Equation is the problem object on which the method acts, not its superclass. Duhamel's Integral is a close accepted-899 neighbor because variation of constants supplies the exact representation from which the scheme is derived, but the integral identity and the numerical method remain different abstractions.
- False position method Domain-specific is a kind of Algorithm
False-position methods are algorithms for solving a declared equation for an unknown.False-position methods are algorithms for solving a declared equation for an unknown.
- Fast-and-Frugal Trees Domain-specific is a kind of Algorithm
A fast-and-frugal tree specializes Algorithm to finite ordered cue tests with one-sided early category exits.For every admissible binary-cue case, the tree prescribes a finite ordered sequence of tests and a determinate terminal category. It satisfies the live Algorithm prime's definite, effective input-to-output procedure, then adds the narrow one-exit/continuation topology and decision-science cue construction.
- Floyd's Cycle-Finding Algorithm Domain-specific is a kind of Algorithm
Floyd's two-speed successor procedure is a specific algorithm for deciding whether one reachable orbit repeats.Given a start state and deterministic successor, the method applies a definite one-step/two-step schedule, tests post-start equality or termination, and produces a justified cycle/no-cycle result; optional passes recover entry and length. These inputs, effective steps, stopping conditions and outputs instantiate Algorithm while adding a particular constant-extra-reference strategy.
- Forward–Backward Algorithm Domain-specific is a kind of Algorithm
Forward–Backward Algorithm is a strict specialization of prime:algorithm: it defines inputs, finite recursive steps, termination after two passes, and posterior-marginal outputs.The broader abstraction is the literal procedural genus. prime:markov_process supplies conditional independence; prime:bayesian_updating explains evidence conditioning; domain_specific:bellman_equation shares temporal recursion. They are components or analogues rather than additional parents. Particle Filter and Variational Message Passing solve related inference problems by different approximations.
- Fourier–Motzkin Elimination Domain-specific is a kind of Algorithm
**`prime:algorithm` (proposed primary parent, strict subsumption).** Fourier–Motzkin is a definite input-to-output procedure with correctness and resource semantics.It specializes Algorithm to sign-partitioned elimination of linear-inequality variables and exact projection. Removing those additions leaves an algorithm; removing procedure leaves no Fourier–Motzkin method.
- Frontal Solver Domain-specific is a kind of Algorithm
**Algorithm** is the strict parent because the frontal method is a terminating constructive procedure with specified inputs, output factorization, correctness, and time/storage bounds.Finite Element Method is a frequent source of local matrices but not a required ontological parent.
- Gauss–Newton Algorithm Domain-specific is a kind of Algorithm
**prime:algorithm** is the broader abstraction this entry instantiates.Gauss–Newton is a repeatable stepwise procedure with defined inputs, transformations, stopping criteria, and output. prime:optimization is a broader problem context. domain_specific:nonlinear_least_squares is the problem class solved rather than a taxonomic parent of a method. Regularization is optional in damped or ill-conditioned variants.
- Greedy Randomized Adaptive Search Procedure Domain-specific is a kind of Algorithm
GRASP is a stepwise randomized construction and local-improvement procedure for combinatorial optimization.GRASP is a stepwise randomized construction and local-improvement procedure for combinatorial optimization.
- Held–Karp algorithm Domain-specific is a kind of Algorithm
The method is a finite exact algorithm organized by dynamic-programming states.What makes it its own entry: subset-and-endpoint dynamic programming that gives exact TSP solutions in O(n-squared times 2-to-the-n) time rather than factorial enumeration.
- Hunt–Szymanski Algorithm Domain-specific is a kind of Algorithm
**prime:algorithm** is the broader abstraction this entry instantiates.Hunt–Szymanski is a deterministic finite procedure with defined inputs, invariants, complexity, and exact output. domain_specific:search_algorithm is a related method family but does not directly taxonomize all LCS dynamic programs. domain_specific:matching concerns pair compatibility, not ordered-chain optimization. Branch and Bound and Greedy Algorithm are declined.
- Hybrid algorithm Domain-specific is a kind of Algorithm
The identity is a composite algorithmic strategy.What makes it its own entry: performance composition by regime-sensitive selection among complete methods.
- In-Place Algorithm Domain-specific is a kind of Algorithm
A strict in-place algorithm is an algorithm distinguished by same-buffer output and a constant counted auxiliary-unit budget.Algorithm supplies a specified input, effective ordered procedure, result, termination contract, and resource behavior. Every admitted In-Place Algorithm has those roles: it transforms a designated input buffer into a result through an effective procedure, while stating the auxiliary-space cost model. Its stable differentia are that the result replaces the designated input storage and the number of counted auxiliary units stays constant as input size grows. Dudek, Gawrychowski and Pokorski demonstrate an array permutation using a constant number of indices; Harvey and Roche demonstrate a truncated Fourier transform using O(1) auxiliary ring elements and pointers. Their units are model-specific, not a common bit bound. An out-of-place transformation or a scratch-array copy-back may be an Algorithm without meeting this child identity. Algorithm's Function Mapping parent relation is conditional and is not promoted to a strict ancestor by this subsumption edge.
- Knuth–Eve Algorithm Domain-specific is a kind of Algorithm
Knuth–Eve instantiates **Algorithm** through a finite preprocessing procedure and a finite evaluator with a correctness invariant.It relates to **Decomposition**, because the polynomial is split into even and odd parts, and to **Optimization**, because the representation minimizes a runtime resource under assumptions. These broad abstractions do not entail the root-conditioned quadratic construction.
- Knuth–Plass Line-Breaking Algorithm Domain-specific is a kind of Algorithm
**`prime:algorithm` — proposed strict subsumption parent.** For a finite paragraph and fixed parameter contract, it is a definite terminating procedure with admissible input, effective steps, a breakpoint/line output, and correctness relative.**`prime:algorithm` — proposed strict subsumption parent.** For a finite paragraph and fixed parameter contract, it is a definite terminating procedure with admissible input, effective steps, a breakpoint/line output, and correctness relative to its least-demerit objective.
- Linear-quadratic regulator rapidly exploring random tree Domain-specific is a kind of Algorithm
Linear-quadratic regulator rapidly exploring random tree is a domain-specific instance of algorithm under its frozen identity. The complete catalog already supplies this broader identity.Linear-quadratic regulator rapidly exploring random tree is a domain-specific instance of algorithm under its frozen identity. The complete catalog already supplies this broader identity.
- Luhn Mod N Algorithm Domain-specific is a kind of Algorithm
Luhn Mod N specializes **Algorithm**: it is a finite deterministic generation/validation procedure with defined input, state, and output.It relates to **Validation**, **Redundancy**, and **Modularity**. None of those entails the alternating Luhn transformation or alphabet mapping.
- Markov algorithm Domain-specific is a kind of Algorithm
It is a finite rule-governed computational procedure.What makes it its own entry: priority-ordered deterministic semi-Thue rewriting as a universal computation model.
- Maze generation algorithm Domain-specific is a kind of Algorithm
It is an automated construction procedure.What makes it its own entry: procedural construction of navigational puzzle topology.
- Method of continued fractions Domain-specific is a kind of Algorithm
The continued-fractions method is a repeatable computational procedure for solving declared integral equations.The continued-fractions method is a repeatable computational procedure for solving declared integral equations.
- Nearest-Neighbor Chain Algorithm Domain-specific is a kind of Algorithm
**Algorithm** is the broader abstraction this entry instantiates: NN-chain is a strict algorithmic procedure with specified state, local-neighbor search, reciprocal-pair test, merge, and termination.Clustering is the result-producing task and application setting, not a superclass of the method. Hierarchical Decomposability describes the output structure rather than the execution mechanism.
- Network Simplex Algorithm Domain-specific is a kind of Algorithm
**`prime:algorithm` — strict subsumption.** Network simplex is a definite iterative procedure mapping a feasible minimum-cost-flow instance and starting-basis construction to an optimal flow or an infeasibility/unboundedness disposition under.**`prime:algorithm` — strict subsumption.** Network simplex is a definite iterative procedure mapping a feasible minimum-cost-flow instance and starting-basis construction to an optimal flow or an infeasibility/unboundedness disposition under its specified variant. It adds a particular representation, pivot rule family, invariants, and stopping certificate to the general algorithm structure. Remove the algorithmic parent and there is no ordered execution or correctness claim; the parent remains meaningful without network flows. **`prime:network_flow_models` — composition / presupposes.** The algorithm presupposes the parent model's directed arcs, costs, capacities, supplies/demands, and conservation equations. Those objects define feasibility, objective value, and dual node potentials. Network Flow Models already mentions network simplex as one possible solver, but does not entail a tree basis or any particular pivot mechanism; many other algorithms solve the same models. **`domain_specific:tree_graph_theory` — composition / presupposes.** The selected basis is a spanning tree, adding one non-tree arc creates exactly one fundamental cycle, and exchanging one cycle arc restores a tree. Those are literal tree-graph-theory consequences, not decorative vocabulary. This direct relation remains useful because `network_flow_models` as a broad parent does not require a tree representation: cost-scaling and successive-shortest-path solvers use the model without it. `prime:linear_programming_lp` is a real broader ancestor but is declined as a direct working parent: the LP structure is already carried through `network_flow_models`, and adding it would not sharpen the child's placement. `prime:optimization` and `prime:duality` are likewise true but transitively or compositionally remote. They belong in explanatory prose and `related`, not in the broader abstraction set.
- Newest Vertex Bisection Domain-specific is a kind of Algorithm
The labeled midpoint-split and conformity-completion rules specify a particular finite mesh-refinement algorithm under admissible initial labeling.Newest vertex bisection has a defined input (a finite, suitably labeled triangular mesh and marked triangles), determinate inherited-edge splits and compatible-neighbor completion, and a refined conforming mesh as output. Under the cited compatibility assumptions its recursive completion terminates. These procedure-defining features make it a specific instance of live Algorithm; the mesh geometry and shape theorem make the child narrower.
- Non-Blocking Algorithm Domain-specific is a kind of Algorithm
A non-blocking algorithm is an executable concurrent procedure with an additional independent-progress condition.The live Algorithm prime is a defined computational procedure. A non-blocking concurrent-object algorithm keeps that procedural identity while requiring operations that remain progress-capable without a stalled thread's exclusive lock release.
- Powerset Construction Domain-specific is a kind of Algorithm
Powerset construction is a finite effective conversion procedure that explores subset states and defines deterministic transitions and acceptance.Given a finite NFA, start from its initial state set, repeatedly compute union successors on input symbols, add newly reached subsets until saturation, and classify a subset as accepting when it meets the source final set. There are at most 2^n subsets, so the exploration terminates; its steps are definite and effective, satisfying live Algorithm. NFA language-preservation supplies the domain-specific differentia.
- Pseudorandom Number Generator Domain-specific is a kind of Algorithm
PRNG is a specialization of `prime:algorithm`.It occupies the tension formalized by `prime:stochasticity_vs_determinism` and relates to Randomness, State Transition, Iteration, and Hashing. Monte Carlo Simulation is a major consumer, not the parent.
- Pseudospectral time-domain method Domain-specific is a kind of Algorithm
The method is a numerical algorithm for wave evolution.What makes it its own entry: spectral spatial accuracy coupled to explicit time-domain wave evolution.
- PTAS Reduction Domain-specific is a kind of Algorithm
**Algorithm** is the strict parent because the reduction certificate is a finite polynomial-time procedure for transforming an instance and tolerance and recovering a source solution with a proved postcondition.Approximation and Translation are close neighbors, but neither alone supplies the executable witness and termination/resource commitments.
- QR Algorithm Domain-specific is a kind of Algorithm
QR Algorithm specializes `prime:algorithm`, the broader abstraction.It instantiates Iteration through repeated similarity steps, Invariance through spectrum preservation, Refinement through deflation, and Decomposition through QR/Schur forms. Jacobi Method is a sibling eigenvalue algorithm rather than an ancestor.
- Random sample consensus Domain-specific is a kind of Algorithm
RANSAC is literally a repeatable randomized problem-solving procedure with explicit sampling, fitting, scoring, stopping, and refinement stages; What makes it its own entry: the random-minimal-hypothesis, thresholded-consensus, best-model, and refit loop, not robust estimation generally, random subsampling alone, or one software library.RANSAC is literally a repeatable randomized problem-solving procedure with explicit sampling, fitting, scoring, stopping, and refinement stages; What makes it its own entry: the random-minimal-hypothesis, thresholded-consensus, best-model, and refit loop, not robust estimation generally, random subsampling alone, or one software library.
- Randomized Algorithm Domain-specific is a kind of Algorithm
A randomized algorithm is an algorithm whose internal random choices affect fixed-input behavior.A randomized algorithm remains a finite executable procedure, with internal random choices as its differentia; deterministic algorithms instantiate the broader Algorithm genus without it.
- Reversible reference system propagation algorithm Domain-specific is a kind of Algorithm
r-RESPA is literally a repeatable state-update algorithm; its operator factorization and molecular-dynamics semantics form the DS residual.What makes it its own entry: the specific reversible reference-system operator splitting and nested force schedule, distinct from generic time stepping or every multiple-time-step implementation.
- Ridders' Method Domain-specific is a kind of Algorithm
Ridders' method is a specified iterative algorithm for finding a continuous real function's bracketed zero.The live Algorithm identity covers finite definite effective procedures. Ridders' method specifies input conditions, midpoint and exponential-fit trial computation, sign-preserving state update and termination criteria. Its numerical-analysis differentia does not make Bisection or False Position a strict parent.
- RNA22 Target-Prediction Algorithm Domain-specific is a kind of Algorithm
RNA22 strictly specializes **Algorithm**.Signal Extraction and Classification describe facets, but one parent is sufficient. Gap Penalty is a scoring neighbor from sequence alignment, not a parent because RNA22’s duplex constraints are not merely an alignment-gap abstraction.
- Search Algorithm Domain-specific is a kind of Algorithm
A search algorithm is an algorithm specialized to exploring a generated state space by a frontier strategy until a goal or stopping report is reached.It has explicit inputs, effective expansion steps, correctness and termination semantics, outputs, and time and space profiles. It adds an initial state, successor function, goal test, frontier-ordering policy, heuristic admissibility, and completeness and optimality guarantees.
- Self-organizing map Domain-specific is a kind of Algorithm
The SOM is literally a repeatable update algorithm with inputs, state, selection, neighborhood update, and stopping conditions; its topology-oriented competitive-learning rule supplies the DS specialization.What makes it its own entry: the lattice-coupled competitive update that jointly organizes prototypes, rather than generic dimensionality reduction, k-means, neural networks, or an already trained two-dimensional visualization.
- Sequential decoding Domain-specific is a kind of Algorithm
The method is a guided search algorithm over code paths.What makes it its own entry: memory-efficient variable-complexity search for long-constraint convolutional codes.
- Shinnar–Le Roux algorithm Domain-specific is a kind of Algorithm
Shinnar–Le Roux algorithm is a domain-specific kind of Algorithm: The Shinnar-Le Roux algorithm transforms between radio-frequency pulse parameters and a pair of polynomials so selective magnetic-resonance excitation profiles can be synthesized and analyzed through recursive filter-like operations.The parent supplies the necessary broader identity—Step-by-step problem-solving procedure.—while the candidate adds the source-domain carrier, recognition rule, and failure conditions. The defining source account begins: The Shinnar–Le Roux (SLR) algorithm designs frequency-selective radiofrequency pulses for magnetic resonance by converting discretized Bloch dynamics into a pair of complex polynomials.
- Sorting Algorithm Domain-specific is a kind of Algorithm
A sorting algorithm is an algorithm specialized to rearranging a finite sequence into a key-defined total order under explicit resource bounds.It supplies admissible input, a determinate terminating procedure, correctness against an ordered-output postcondition, and time and space costs. It adds comparison or key structure, stability and memory axes, the decision-tree lower bound, and a repertoire of sorting procedures.
- Stable Sort Domain-specific is a kind of Algorithm
Stable Sort is a domain-specific kind of algorithm under its frozen identity and differentia. Complete-catalog comparison found the corresponding live broader identity.Stable Sort is a domain-specific kind of algorithm under its frozen identity and differentia. Complete-catalog comparison found the corresponding live broader identity.
- Steensgaard's algorithm Domain-specific is a kind of Algorithm
It is a specific scalable analysis algorithm.What makes it its own entry: unification-based alias analysis trading precision for near-linear scalability.
- Swedish Interactive Thresholding Algorithm Domain-specific is a kind of Algorithm
SITA is a strict specialization of **Algorithm**: it is a defined procedure mapping a perimetric test configuration and sequential patient responses to local threshold estimates and reliability information.Measurement is constitutive context and Adaptive Control is structurally related, but adding either as another direct parent would obscure the minimal algorithmic identity.
- Tate's Algorithm Domain-specific is a kind of Algorithm
Tate's algorithm is an effective terminating local-arithmetic decision procedure with a finite resource account on its declared valid input domain.Every admitted instance starts with nonsingular elliptic Weierstrass data and a selected finite place in an effective arithmetic representation, applies prescribed normalization, divisibility and residue-root tests with minimality control, and returns local reduction data. Translations preserve the curve and discriminant; nonminimal weighted scaling decreases the integral discriminant valuation, and local refinement cannot continue beyond the finite valuation of a nonsingular model. Exact arithmetic and finite-residue polynomial operations are effective; the fixed control flow has a finite symbolic time and space account independent of any one software implementation. Tate's stable differentia is the elliptic-curve and place input and its ordered reduction and minimality classification. The Algorithm to Function Mapping edge remains conditional.
- Ternary search Domain-specific is a kind of Algorithm
It remains its own entry because its identity is fixed by the ordered domain, unimodality and strictness assumptions, minimization or maximization direction, probe placement, tie rule, discrete or continuous termination, evaluation precision, and complexity.It remains its own entry because its identity is fixed by the ordered domain, unimodality and strictness assumptions, minimization or maximization direction, probe placement, tie rule, discrete or continuous termination, evaluation precision, and complexity.
- Thompson Sampling Domain-specific is a kind of Algorithm
Thompson Sampling is a domain-specific kind of algorithm under its frozen identity and differentia.Thompson Sampling is a domain-specific kind of algorithm under its frozen identity and differentia.
- Topological Sorting Domain-specific is a kind of Algorithm
Topological sorting is an algorithm specialized to producing a linear extension of a precedence DAG or reporting a cycle in linear time.Kahn's in-degree sweep and DFS post-order are finite effective procedures with defined inputs, outputs, termination, correctness, and O(V+E) cost. The child fixes the input to a directed precedence graph and the output to one total order respecting every edge.
- Tournament sort Domain-specific is a kind of Algorithm
It is a sorting procedure organized as repeated tournament updates.What makes it its own entry: selection sorting accelerated by reusable comparison-tournament structure.
- Tree Sort Domain-specific is a kind of Algorithm
The accepted reference-grade review places Tree Sort under Algorithm because the child instantiates or depends on the parent's broader structure while retaining its own constitutive identity.A comparison-sorting method that inserts items into a search tree and emits them by in-order traversal, making output order depend on the tree invariant and runtime depend on tree height. The parent is defined more broadly: Step-by-step problem-solving procedure.
- Trellis quantization Domain-specific is a kind of Algorithm
The candidate is literally a finite dynamic-programming or shortest-path procedure over trellis states; its quantization and codec rate-distortion semantics supply the DS specialization.What makes it its own entry: the trellis-coupled block decision and rate-distortion path metric, not scalar quantization, trellis-coded modulation, generic rate control, or a codec option named trellis without a reconstructable search.
- Trial Division Domain-specific is a kind of Algorithm
Trial division is a finite exact-search algorithm over bounded proper-divisor candidates.For each supported carrier, trial division specifies a target, a finite adequate candidate set, exact divisibility tests, a complete stopping bound and a factor/no-factor result. These satisfy the live Algorithm's procedure and termination signature; algebraic divisor search is the narrower differentia.
- Truth-table reduction Domain-specific is a kind of Algorithm
A truth-table reduction is witnessed by a finite effective input-to-query-to-output procedure with a correctness contract.Its oracle semantics, nonadaptive batch, and Boolean combination provide the autonomous computability-theoretic residual. What makes it its own entry: the finite nonadaptive query batch plus an input-computable Boolean truth table and total correctness guarantee, not generic logical truth tables, arbitrary oracle computation, many-one coding, or merely a computable bound on adaptive use.
- Type Inference Domain-specific is a kind of Algorithm
Type inference is an algorithm specialized to generating and unifying typing constraints to return a principal type or a located type error.In its stated Hindley-Milner discipline it has admissible expressions, finite syntax-directed constraint generation, a terminating unification solver, a success or conflict result, and known complexity. The type language and principal-type guarantee supply the differentia.
- Unicode Collation Algorithm Domain-specific is a kind of Algorithm
Unicode Collation Algorithm is a strict domain-specific instance of **`prime:algorithm`**.It takes Unicode strings plus a collation table and settings, executes a definite mapping-and-key procedure, and yields a comparison outcome. It adds a particular Unicode equivalence discipline, multilevel data model, tailoring system, and conformance contract. Removing the procedure removes the candidate's identity; the parent remains meaningful without any of those additions. This is the strongest taxonomic parent. It presupposes and realizes **`prime:order`**. A collator establishes a total comparison order or, at strengths that intentionally collapse distinctions, a total preorder over strings. The level-prioritized weights and the table's well-formedness supply the relation; UCA is not merely an unordered transform. `Order` remains broader and already carries comparison as a prerequisite, so a separate direct parent edge to `comparison` would be redundant in a minimal placement even though comparison is an important related prime. It contains an instance of **`prime:canonical_form`** through NFD-equivalent processing. Canonically equivalent Unicode sequences must receive the same comparison behavior, and the logical main algorithm begins by converting each string to the canonical-decomposition normal form. This is a constitutive operation rather than the taxonomic identity: canonical form alone does not supply linguistic weights, strength levels, tailoring, or sort keys. The live **`domain_specific:sorting_algorithm`** is a strong neighbor, not a parent. UCA supplies a comparison/key function that a sorting algorithm may call; it does not itself rearrange a finite sequence or choose a stability, memory, adaptivity, or asymptotic-complexity strategy. Treating UCA as a species of Sorting Algorithm would collapse comparator semantics into the separate procedure that consumes them.
- Variable Elimination Domain-specific is a kind of Algorithm
Variable Elimination specializes `prime:algorithm`: inputs, ordered effective steps, exact output, termination, and resource bounds are explicit.It also relates to `prime:factorization`, which makes local processing possible, and `prime:dynamic_programming`, through reusable intermediate summaries. Algorithm is the broader abstraction this entry instantiates; Factorization is a prerequisite, not the entire method.
- Verification-based message-passing algorithms in compressed sensing Domain-specific is a kind of Algorithm
Verification-based message-passing methods are algorithms for sparse-signal recovery.Verification-based message-passing methods are algorithms for sparse-signal recovery.
- Verlet Integration Domain-specific is a kind of Algorithm
Verlet Integration specializes `prime:algorithm`: it is a definite finite update procedure with inputs, outputs, accuracy, stability, and resource bounds.It relates to `prime:approximation` through discretization and to `prime:invariance` through symplectic/time-reversal structure. Algorithm is the broader abstraction this entry instantiates.
- Vincenty's formulae Domain-specific is a kind of Algorithm
Vincenty's formulae is a domain-specific instance of algorithm under its frozen identity. The complete catalog already supplies this broader identity.Vincenty's formulae is a domain-specific instance of algorithm under its frozen identity. The complete catalog already supplies this broader identity.
- Yannakakis Algorithm for Acyclic Joins Domain-specific is a kind of Algorithm
**`prime:algorithm` — proposed strict subsumption parent.** Yannakakis has a finite input, effective ordered steps, termination, correctness condition, output, and resource bound.The child adds the alpha-acyclic relational substrate and exact reduction/output contract.
- Yo-Yo Leader-Election Algorithm Domain-specific is a kind of Algorithm
The broader abstraction is `prime:algorithm`: Yo-Yo is a finite, specified procedure mapping an identified connected network to a leader designation, with correctness and termination obligations.It also instantiates comparison, prioritization, feedback, and iteration. Those primes illuminate operations but do not supply a more literal genus than Algorithm. Leader election itself is the problem family, not the broader abstraction. A method/result boundary would be crossed by calling the algorithm a specialization of a leader state. The sole DAG proposal therefore remains Algorithm, and no structured or live edge is written.
- Ziggurat Algorithm Domain-specific is a kind of Algorithm
Ziggurat Algorithm is a strict specialization of `prime:algorithm`: it is a finite executable procedure with precomputation, random inputs, branching tests, and an output contract.It is related to `prime:monte_carlo_simulation` because it supplies target-distributed random inputs to simulations, but generation of one exact variate does not itself approximate a quantity by repeated sampling. Monte Carlo Simulation is therefore a common consumer rather than the broader abstraction. No accepted-899 Rejection Sampling node exists as a literal endpoint in the frozen catalog. That absence does not authorize inventing one or treating every rejection sampler as Ziggurat. The broader abstraction remains Algorithm.
- Bailey–Borwein–Plouffe Formula Domain-specific presupposes Algorithm
The broader abstraction is `prime:algorithm` by strict compositional presupposition.The node's defining non-sequential access property depends on a finite, definite procedure with target position as input, modular-exponentiation and tail-summation steps, termination rules, an output block, correctness, and time/space bounds. The exact series is the mathematical enabler; the parent supplies the procedure that turns it into digit access. `prime:convergence` is a required analytic mechanism for controlling the infinite tail, and modular arithmetic is central to the head. They are related mechanisms rather than proposed parents because convergence alone covers countless non-extracting series and the catalog has no exact live Modular Arithmetic node. `prime:decomposition` is also related through the lane split and head-tail split. The frozen semantic match to Slow-Growing Hierarchy is rejected: both are mathematical, but one classifies ordinal-indexed functions and the other is a radix-specific series identity and algorithm.
- Linear-on-the-Fly Testing Domain-specific includes Algorithm
An assembly algorithm is an internal constituent of each LOFT administration.Every admitted LOFT administration contains a form-assembly algorithm mapping a pool and specification to a delivered form. The algorithm is an identity-bearing internal component of the testing method, while Algorithm occurs across many other substrates. LOFT is not simply a species of an algorithm, and the algorithm is not merely an external prerequisite; this is parent-in-child composition/part_of.
- Quantum Computing Domain-specific presupposes Algorithm
Quantum Computing presupposes Algorithm: the parent's defining role is necessary to the child's frozen mechanism or criterion.The reviewed Quantum Computing identity—A computational paradigm that encodes and transforms information in controlled quantum states, using superposition, interference, entanglement, measurement, and error management to implement algorithms whose resource behavior can differ from classical computation—requires the structural role carried by Algorithm—Step-by-step problem-solving procedure; removing that role makes the child mechanism or criterion undefined. Algorithm can occur in settings that do not instantiate Quantum Computing, so this is dependency rather than subsumption.
- Computability Prime presupposes Algorithm
Per dossier and file: computability is 'the boundary/meta-level relation that algorithm presupposes' — the existence-question (does an effective procedure exist at all?) over algorithm's central object.Per dossier + file: computability is 'the boundary/meta-level relation that algorithm presupposes' — the existence-question (does an effective procedure exist at all?) over algorithm's central object. algorithm is the positive object, computability the partition between buildable and provably-unbuildable. Presupposes the notion of effective procedure.
Hierarchy path (1) — routes to 1 parentless root
- Algorithm → presupposes, conditional Function (Mapping)
Neighborhood in Abstraction Space¶
Algorithm sits among the more crowded primes in the catalog (26th percentile for distinctiveness): several abstractions describe nearly the same structure, so a description that fits it will tend to fit its neighbors too — transporting it usually means disambiguating within this family rather than landing on it exactly.
Family — Complexity Limits & Algorithmic Tradeoffs (12 primes)
Nearest neighbors
- Iteration — 0.77
- Computability — 0.75
- Function (Mapping) — 0.73
- Fixed Point — 0.72
- Recursion — 0.72
Computed from structural-signature embeddings · 2026-10-25
Not to Be Confused With¶
An algorithm must be distinguished from Transformation, the broader concept of input-to-output mapping. A transformation is a general mapping rule or function describing the relationship between inputs and outputs—what the output should be given any input. An algorithm is a procedure: not just what the output should be, but the finite sequence of prescribed, unambiguous steps that must be executed to produce it. A transformation specifies the relationship; an algorithm specifies how to compute it step-by-step. The transformation "multiply x by 2" is abstract; the algorithm for multiplying large integers by hand specifies the order of digit-wise operations, carries, and accumulation. Many different algorithms can implement the same transformation (quicksort and mergesort both sort, but they use different procedures); some transformations have no algorithm at all (the halting problem has no algorithm, even though the transformation is well-defined).
An algorithm is also not Recursion, a specific control structure that some algorithms employ. Recursion is the pattern where a function calls itself with reduced problem size, eventually reaching a base case. Algorithms may use recursion (quicksort uses recursive partitioning), but they also use iteration, conditionals, and other control structures. Iteration alone (repeating an action until a condition is met) is not recursion; an algorithm may be entirely iterative. A linear search iterating through a list is an algorithm that uses iteration, not recursion. Recursion is a technique available to algorithms; it is not the defining feature of what makes a procedure an algorithm.
Nor is an algorithm identical to a Heuristic, though the terms are often confused in casual use. A heuristic is a practical rule or shortcut that produces good (but not guaranteed optimal) results efficiently—it trades correctness for speed. A medical heuristic might be "treat common diseases first when symptoms are ambiguous." An algorithm, in the formal sense, is a step-by-step procedure that is guaranteed to terminate with specified correctness properties. Many practical "algorithms" in software are actually heuristics—they perform well on typical inputs but lack correctness guarantees. The distinction matters: if you need guaranteed correctness, a heuristic is insufficient; if you can tolerate approximate solutions quickly, a heuristic is better than a slow algorithm.
An algorithm is also not Iteration, the simple repetition of a process. Iteration is one control mechanism (repeat action until condition); an algorithm is the full procedure with logic, data transformations, conditionals, and termination. An iterative loop is a component of many algorithms, but iteration alone does not define an algorithm. A while-loop that repeats "add 1 to counter" is iteration, but it's not a complete algorithm unless combined with initialization, a termination condition, and a clear purpose. Algorithms specify not just the repetitive structure but the overall logical flow.
Finally, an algorithm is not Sequencing, the ordering of actions in time. Sequencing is the temporal arrangement—do step A, then step B, then step C. An algorithm specifies not just the sequence but the logical control flow, conditionals, and data transformations. A cooking sequence ("first chop, then cook, then serve") is ordered actions; an algorithm specifies which cuts, which heat, which timing, and what conditional branches (adjust heat if temperature exceeds threshold). Sequencing is the ordering; an algorithm is the complete executable procedure with all specifications necessary for mechanical execution.
Solution Archetypes¶
Solution archetypes in the catalog that build on this prime — directly (this prime is a source ingredient) or as a related prime.
Built directly on this prime (9)
- Complexity Scaling Assessment: Assess how effort, cost, time, memory, or coordination burden grows as input size or system scale increases.▸ Mechanisms (9)
- Algorithm Benchmarking — Runs candidate algorithms or procedures at a ladder of input sizes to measure the real resource-growth curve, catch performance cliffs, and pick the implementation that holds up at scale.
- Capacity Planning Model — Translates a forecast of future demand into the servers, staff, budget, and review capacity it will require, against known limits and a deliberate buffer.
- Computational Complexity Analysis — Once a problem is known solvable in principle, measures how its cost grows with input size to place it in a complexity class and separate the tractable from the merely computable.
- Coordination Cost Modeling — Estimates how communication, sync, and approval burden grows as actors and dependencies multiply — often super-linearly with pairwise ties, not linearly with headcount.
- Organizational Complexity Review — A recurring review that examines how governance layers, role count, decision rights, and meeting load are growing with the organization — and whether a restructure is due.
- Process Scalability Audit — Walks a specific workflow step by step to find the approvals, queues, exceptions, and handoffs that become intolerable as volume or variety rises — and lists the redesigns that would relieve them.
- Queueing Simulation — Models arrivals, service times, and capacity to predict how waiting time and backlog explode as utilization approaches its limit — capturing the effect of variability, not just averages.
- Scale Pilot or Dry Run — Stages a limited real-world rehearsal of a chosen future-scale scenario to surface the hidden overhead, staffing gaps, and broken assumptions a desk estimate cannot see.
- Workload Scaling Test — Drives increasing synthetic load against the real deployed system to find where throughput, latency, and error rate break — the saturation point and the headroom before it.
- Computability Boundary Mapping: Before optimizing or automating a problem, determine whether any correct terminating procedure can solve the declared class, prove that boundary, and publish a weaker but honest fallback when it cannot.▸ Mechanisms (18)
- Abstract Interpretation or Model Checking — Decides a property soundly on a finite abstraction of an otherwise-undecidable system, trading exactness for a guaranteed answer that never misses a real violation.
- Bounded-Domain Exhaustive Search — Turns a question that is undecidable in general into a decidable one by fixing a finite bound and mechanically checking every case inside it.
- Computability Boundary Decision Record — Records where a project drew the computability boundary, which guarantee it will ship, and what would force the line to be redrawn.
- Computational Complexity Analysis — Once a problem is known solvable in principle, measures how its cost grows with input size to place it in a complexity class and separate the tractable from the merely computable.
- Constructive Algorithm and Correctness Proof — Settles a problem on the decidable side by exhibiting an actual algorithm and proving it both total and correct — the proof and the procedure are one object.
- Diagonalization Impossibility Proof — Proves that no algorithm can decide a class by constructing, from any candidate decider, a self-referential input on which it must be wrong.
- Enumeration and Dovetailing — Semi-decides a class by fairly interleaving all candidate computations, halting 'yes' the moment one succeeds and otherwise running on — buying a complete yes-side at the cost of no honest 'no'.
- Fallback-Mode Router — Dispatches each query to the strongest method that fits where it falls relative to the computability boundary — exact, sound-approximate, bounded, or escalated — under an explicit fallback contract.
- Halting-Problem Reduction — Proves a target problem undecidable by wiring a known-undecidable problem (canonically the halting problem) into it, so effort on a universal solver stops before it starts.
- Language-Fragment Restriction — Regains a terminating decision procedure by narrowing the language problems are stated in to a syntactic fragment known to be decidable, trading expressive power for a guaranteed answer.
- Many-One Reduction Proof — Transfers a problem's decidability or hardness verdict along a single total computable map that preserves membership, exhibiting the mapping itself as the proof.
- Promise-Problem Restriction — Makes a hard problem solvable by narrowing the inputs the solver is accountable for to those meeting a stated promise, leaving promise-violating inputs as don't-cares.
- Proof by Counterexample — Refutes an over-broad universal claim — that some method handles an entire class — by exhibiting one well-formed instance on which it demonstrably fails.
- Proof Checking — Independently re-verifies a decidability or impossibility proof step by step, so the boundary claim rests on a checked argument rather than on its author's authority.
- Reduction-Direction Checklist — A pre-flight check that a reduction runs from the known-hard problem into the target — the direction that actually proves hardness — with every assumption named before the verdict is trusted.
- Semi-Decision with Explicit Unknown — Runs a sound one-sided recognizer that confirms YES when it can, but returns an explicit UNKNOWN at a declared resource bound instead of looping forever or faking a NO.
- Theorem-Prover-Guided Search — Uses an automated or interactive prover to search for and mechanically check the proof or certificate a boundary claim rests on, recording the verified guarantee and any open residue.
- Turing-Reduction Analysis — Asks whether a problem becomes solvable given an oracle for another, placing it among the degrees of relative computability rather than in a flat decidable/undecidable split.
- Constraint-Guided Backtracking: Solve a constrained, path-dependent problem by extending a partial solution, testing it early, and undoing the latest failed commitment while preserving still-valid prior work.▸ Mechanisms (7)
- Chronological Backtracking Log — An append-only, reason-annotated record of every choice, failure, and rollback in the order it happened, so a dead branch is never retried and any contradiction can be traced to its cause.
- Constraint-Satisfaction Solver Pass — Encodes the commitments as a formal constraint model and runs a solver that propagates them to a reduced feasible region — or mechanically detects that no joint solution exists.
- Decision-Tree Search Diagram — A drawn tree whose nodes are partial states and whose branches, laid out by priority, show at a glance where the search stands, which subtrees are exhausted, and which alternatives remain open.
- Forward-Checking Table — A table that, after each tentative commitment, recomputes the surviving legal options for every undecided part and flags a doomed branch the moment any part runs out.
- Hypothesis-Tree Review — A structured human checkpoint that walks the tree of live and refuted hypotheses, judges which branches are genuinely closed, and chooses where to resume or when to escalate.
- Recursive Depth-First Backtracking — A recursive method that extends a partial state one commitment at a time and returns to the prior choice point when a branch cannot complete.
- Undo-Stack Protocol — A state-preserving protocol that records each step as a reversible entry and restores the exact prior coherent state when a step must be undone.
- Decision-Procedure Boundary Mapping: Map whether a yes/no question can be decided by a finite total procedure before promising automation, certainty, or universal adjudication.▸ Mechanisms (5)
- Decidability Triage Worksheet — Walks a team, at design time, through the questions that reveal whether a yes/no problem can be a real decision procedure — and where it can't, routes it to a declared fallback.
- Decision-Procedure Specification — Pins down, in writing, the algorithm a decision rests on: exactly which inputs it accepts, what each output means, that it always halts, and why its answers are correct.
- Fallback Mode Register — A living ledger of every case the procedure cannot cleanly decide, paired with the named fallback it is routed to — bounded search, heuristic, semi-decision, approximation, human review, or scope renegotiation.
- Reduction Boundary Map — Locates a new yes/no question by mapping it onto problems whose difficulty is already known — decidable, undecidable, complete-for-a-class, or merely bounded — so you inherit the verdict instead of re-deriving it.
- Termination & Totality Proof Review — Stress-tests a proposed procedure against two claims: that it halts for every input in scope, and that when it halts it returns one of the answers it is allowed to return.
- Greedy Stepwise Commitment: Build a solution one locally best irreversible step at a time when full lookahead is too costly and the local score is trusted for the problem class.▸ Mechanisms (12)
- Dijkstra-Style Frontier Expansion — Grows a solution outward by permanently settling the cheapest-reachable node next — safe precisely because every step's cost is non-negative.
- Earliest-Deadline-First Dispatch — Always dispatches the job with the nearest deadline next, trading away future flexibility to hold down the worst lateness when urgency is what matters.
- Greedy Assignment Pass — Seals the single highest-fit pairing available right now, decrements both sides' capacity, and never revisits it — one irreversible sweep through a matching problem.
- Greedy Set-Cover Heuristic — Repeatedly adds the candidate covering the most still-uncovered need per unit cost — cheap, transparent, and provably within a logarithmic factor of the smallest possible cover.
- Highest-Marginal-Gain-First Rule — At each step adds the option with the largest immediate improvement per unit of cost it consumes — scoring the gain against what's already been chosen, not in isolation.
- Kruskal-Style Edge Acceptance — Considers candidate connections cheapest-first and accepts each only if it doesn't break a structural invariant — exactly optimal when the legal sets form a matroid.
- Lexicographic Priority Rule — Ranks each choice by a fixed hierarchy of criteria, consulting a lower criterion only to break ties left by the ones above it — never trading a worse top criterion for a better lower one.
- Nearest-Neighbor Route Extension — Grows a path by repeatedly stepping to the nearest still-available point, letting the current endpoint alone decide the next move.
- Priority-Queue Step Selection — Keeps every feasible candidate in a priority queue and repeatedly commits the current best, re-prioritizing the rest as each commitment reshapes the residual state.
- Shortest-Processing-Time-First Rule — Commits the shortest job first — exploiting the fact that clearing quick work early minimizes total waiting, but only when average wait is genuinely the objective.
- Sorted Candidate Sweep — Scores and sorts every candidate once, then makes a single pass accepting each in order whenever it keeps the solution feasible — no re-scoring, no revisiting.
- Trap-Sentinel Escalation — Watches a greedy run for signs it has walked into a trap and, when tripped, escalates from cheap local repair to bounded lookahead to full rollback.
- Heuristic vs. Algorithm Tradeoff and Selection: Choose the decision method, not just the decision: use heuristics where speed and bounded cost dominate, algorithms where rigor and consistency are worth the burden, and hybrids where staged escalation is safest.▸ Mechanisms (8)
- Algorithmic Escalation Protocol — Routes decisions above threshold to formal analysis, optimization, simulation, model review, or independent adjudication.
- Decision Method Triage Matrix — Scores or classifies decisions by stakes, urgency, reversibility, uncertainty, data quality, and accountability need.
- Heuristic Boundary Checklist — Confirms whether a shortcut is valid in the current domain, population, feedback regime, and risk level.
- Model or Rule Card — Documents intended use, constraints, known failure modes, data assumptions, explainability, and review owner for the selected method.
- Override and Exception Log — Records when users depart from the default method, why, and whether exceptions reveal a boundary failure.
- Retrospective Error Calibration Review — Reviews outcomes and error patterns to tune thresholds, heuristics, algorithms, and hybrid pathways.
- Shadow-Mode Method Comparison — Compares heuristic and algorithmic outputs before switching operational authority.
- Stakes–Latency–Error Scorecard — Makes the central tradeoff visible by juxtaposing consequence, time budget, and expected error reduction.
- Operation-Weighted Data Structure Design: Choose the information structure around the real operation mix, making lookup, update, traversal, storage, consistency, and maintenance tradeoffs explicit instead of accidental.▸ Mechanisms (11)
- Abstract Data Type Interface — Fixes the operations and guarantees a structure must offer while hiding how it stores them, so callers depend on behaviour, not representation.
- Adjacency List or Matrix — Stores a graph as per-vertex neighbour lists or a full vertex-by-vertex matrix, trading space for the speed of the traversal and edge-tests the workload leans on.
- Columnar or Row Layout — Orients physical storage by row or by column to match whether the workload fetches whole records or scans a few fields across many rows.
- Entity-Relationship Schema — Models the domain as entities, relationships, keys, and cardinalities so identity and referential integrity are enforced by the shape of the data itself.
- Hash Table or Key-Value Store — Places each record in a slot computed from a hash of its key, so exact-match lookup, insert, and delete run in near-constant time — at the cost of any order among them.
- Materialized View or Cache — Precomputes and stores the answer to a costly query so reads hit a ready-made result, at the price of keeping it fresh as the base data changes.
- Normalized / Denormalized Schema Pair — Keeps one normalized, redundancy-free form as the authoritative source for correct writes and a denormalized, pre-joined form for fast reads — with an explicit rule for which is the truth.
- Schema Migration Runbook — A staged, reversible procedure for reshaping a live data structure — expand, backfill, switch, contract — so the system keeps serving reads and writes throughout and can roll back at each step.
- Serialization Format and Codec — Fixes how in-memory structures cross to bytes and back — a shared format contract that lets independent writers and readers persist and exchange data without sharing memory.
- Tree or B-Tree Index — Keeps keys in sorted, balanced order so point lookups and range scans both run in logarithmic time, with node fanout sized to the storage block.
- Workload Benchmark and Trace — Captures the real operation mix and access patterns from a running system, then replays them against candidate structures — so the design is weighted by measured demand instead of guessed.
- Problem-Distribution Fit Selection: Select and tune methods by their fit to the expected problem distribution, because no optimizer, learner, search procedure, or decision rule is best averaged across all possible worlds.▸ Mechanisms (12)
- Algorithm Portfolio Router — Keeps a registry of methods and, case by case, dispatches each instance to the member whose bias fits that instance's regime — turning 'pick one winner' into 'pick the right specialist for this case,' and re-routing as the regime shifts.
- Assumption Register — A shared record of the premises a plan is betting on — each with its evidence basis, an owner, and an expiry or invalidation condition — so the beliefs holding up a decision are named and re-checked rather than silently assumed true forever.
- Baseline Comparison Table — Scores the candidate method head-to-head against a deliberately assembled ladder of reference points — trivial, incumbent, simple-but-strong, robust, domain-specific, and human-assisted — under identical conditions, so an apparent win has to survive comparison with what it claims to beat.
- Benchmark Refresh Audit — A recurring check that the benchmark tasks, reference data, and pass/fail thresholds still resemble the live problem distribution — refreshing them on a cadence before the evaluation quietly stops measuring reality.
- Challenge Case Red Team — Charters people whose explicit job is to break the method — hunting for the inputs where its assumptions fail or its bias does harm — and refuses to let it through the gate until domain experts have tried and failed to break it.
- Method Bias Matrix — Lays candidate methods side by side by the inductive bias each one carries — its assumptions, the structures it favors, and the regime where that bias turns into a blind spot — so selection can match bias to the problem's shape before anything is benchmarked.
- Method Card or Model Card — A published, standardized card that states a method's intended and out-of-scope uses, its performance broken out by condition, and the tradeoffs each stakeholder inherits — so downstream users receive the method's limits, not just its headline number.
- No-Universal-Winner Claim Review — Stops any 'this method is simply the best' claim at the gate and sends it back until it names the reference class it applies to, the evidence behind it, and the boundary of problems where it actually holds.
- Out-of-Distribution Monitor — Watches live inputs for cases that no longer resemble the distribution the method was chosen for, and raises a flag — and a retune-or-switch trigger — before the method's fit silently expires.
- Problem Distribution Profile — Documents the problems the system will actually face — their types, frequencies, uncertainty, constraints, and the cost of getting each wrong — so a method is chosen to fit that mix rather than to win a generic benchmark.
- Regularization Path Review — Sweeps a method's complexity penalty or prior across its whole range and reads how fit, generalization, and failure modes change along the path, so the inductive bias is set to match the problem instead of left at a default.
- Stratified Benchmark Suite — Builds the test set as explicit per-regime strata — noise levels, subgroups, scales, scenario types — and reports each separately, so a method cannot win by acing the common cases while quietly failing the ones that matter.
- Proceduralization: Convert tacit or inconsistent work into explicit repeatable steps with inputs, outputs, and exception handling.▸ Mechanisms (10)
- Automation Routine — Encodes a validated procedure so a machine runs the normal path itself — reading a triggering input, applying coded rules, and emitting the output — while diverting abnormal cases to a human.
- Checklist
- Decision Tree
- Playbook — Packages a family of pre-built response plays so that, once you recognize which situation you are in, you can pull the matching play, know who runs it, and know when it is over.
- Process Map — Draws the whole task as a diagram — boundaries, steps, branch points, and the handoffs between lanes — so the real shape of the work becomes visible before anyone tries to fix or formalize it.
- Protocol — A formally authorized sequence whose signature is mandatory verification — preconditions that must be confirmed, checkpoints that must pass, and an evidence trail that proves the sanctioned steps were followed.
- Runbook — A step-by-step operating procedure for running or recovering a system under pressure, built around the stop-and-roll-back condition and the branch to take when a step fails.
- Standard Operating Procedure — Freezes a stabilized, low-judgment routine into ordered steps, named roles, and explicit acceptance conditions so anyone can run it the same way.
- Swimlane Workflow Diagram
- Workflow Script — Encodes a multi-actor process so an engine drives it — sequencing tasks, routing each handoff to its owner, and closing the case at the end — while the owners still do the work.
Also a related prime in 15 archetypes
- Assumption-Bounded Distributed Agreement: Make distributed agreement achievable by declaring the fault, timing, membership, and validity model, preserving safety when progress is uncertain, and using only decision evidence that is valid under those assumptions.
- Bounded-Rationality Decision Design: Match decision method, search depth, sufficiency threshold, and escalation to the real limits and stakes of the choice.
- Constraint Propagation and Decoupling: When constraints bind a problem into an unwieldy whole, propagate their implications first, then solve only the reduced and justified subproblems that remain.
- Demand-Triggered Deferred Evaluation: Represent optional or path-dependent work as a suspended unit, realize only the dependency closure demanded now, and make result sharing, side effects, failure timing, cancellation, lifetime, and first-use latency explicit.
- Discrete–Continuous Model Selection: Choose whether to model a process as discrete steps or continuous flow based on what must be measured, controlled, or decided.
- Dominant-Term Regime Modeling: Model what will matter at scale by identifying the dominant term in a limiting regime, classifying behavior by growth order, and treating lower-order detail as conditional residue rather than as the main guide.
- Dynamic Subproblem Reuse: Reuse solutions to recurring subproblems so repeated decision work does not have to be recomputed.
- Equivalence-Preserving Rewrite Optimization: Rewrite something into a cheaper, clearer, faster, safer, or more usable form only after proving or testing that the declared behavior stays equivalent.
- Formal Derivation System Design: Turn reasoning into an explicit symbolic machine by fixing symbols, well-formedness rules, axioms, inference rules, and derivation checks.
- Grammar-Guided Structure Recovery: Recover the nested structure carried by a flat sequence by binding the input to a grammar, preserving spans, retaining competing parses when needed, and validating the selected hierarchy.
Notes¶
The distinction between algorithm (procedure), function (input-output relation), and heuristic (approximate procedure without guarantees) is foundational to computer science and mathematics. Algorithms are also intimately tied to computability theory (Turing 1936, Church 1936) and the notion of "effective procedure." The design and analysis of algorithms remains one of computer science's central preoccupations, with rich subareas in sorting, searching, optimization, and graph algorithms.
References¶
[1] Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley. ISBN 9780201896831. Canonical source for the formal definition of an algorithm via its five properties — finiteness, definiteness, input, output, and effectiveness. registry ↩
[2] Motwani, R., & Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press. Canonical reference unifying deterministic and randomized algorithms as input-to-output mappings, distinguishing Las Vegas from Monte Carlo procedures. registry ↩
[3] Hoare, C. A. R. (1969). "An Axiomatic Basis for Computer Programming." Communications of the ACM, 12(10), 576–580. Introduces Hoare logic with precondition/postcondition assertions as the formal framework for proving partial correctness (and, with termination, total correctness) of programs. registry ↩ Show verification details
Supported in partVerified against the work's full text
Hoare gives pre/postcondition assertions and a loop invariant for conditional correctness, but explicitly says his axioms give no basis for proving termination.
“is that they give no basis for a proof that a program suc- cessfully terminates.”
[4] Hartmanis, J., & Stearns, R. E. (1965). "On the Computational Complexity of Algorithms." Transactions of the American Mathematical Society, 117, 285–306. Founding paper of computational complexity theory: defines time- and space-bounded computation and proves hierarchy theorems. registry ↩
[5] Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society, s2-42(1), 230–265. Defines computability via the abstract Turing machine, establishing machine-model independence as the criterion for an effective procedure. registry ↩
[6] Bishop, E. (1967). Foundations of Constructive Analysis. McGraw-Hill. Founds constructive analysis, distinguishing non-constructive existential proofs from constructive proofs whose 'performable operations' produce explicit results. registry ↩
[7] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Defines an algorithm as 'any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output' — the verbatim definition the prime quotes on FACT-D30-007. registry ↩
[8] Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik, 1(1), 269–271. Original presentation of the shortest-path algorithm — a finite, definite procedure with provable correctness on graphs with non-negative edge weights. registry ↩
[9] Gawande, A. (2009). The Checklist Manifesto: How to Get Things Right. Metropolitan Books. Cross-domain analysis of checklists (aviation preflight, surgical safety, construction) as definite step-by-step procedures producing reliable outputs independent of operator judgment. registry ↩
[10] Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. Classical algorithm-design/analysis text establishing a rigorous framework for designing efficient algorithms and analysing worst-case complexity. registry ↩
[11] Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley. Foundational study formalizing heuristics as strategies that guide search along promising paths but may yield suboptimal solutions or fail to terminate — sharply distinguishing them from algorithms with provable guarantees, supporting the T2 algorithm-vs-heuristic distinction on FACT-D30-011. registry ↩
[12] Goldberg, D. (1991). "What Every Computer Scientist Should Know About Floating-Point Arithmetic." ACM Computing Surveys, 23(1), 5–48. Canonical survey of how finite-precision floating-point implementation diverges from abstract real-number computation, producing rounding error, cancellation, and overflow not visible at the specification level. registry ↩ Show verification details
Supported in partVerified against the work's full text
Gives concrete cases where reasoning from real-number semantics goes wrong in the implementation, notably compiler optimizations; it does not say this is a common failure of algorithm reasoning in general.
“These examples can be summarized by saying that optimizers should be extremely cautious when applying algebraic identities that hold for the mathematical real numbers to expressions involving floating-point variables.”
[13] Karp, R. M. (1991). "An Introduction to Randomized Algorithms." Discrete Applied Mathematics, 34(1–3), 165–201. Surveys algorithms that make random choices and distinguishes deterministic, Las Vegas, and Monte Carlo classes with their respective worst-case/expected/probabilistic guarantees. registry ↩
[14] Floyd, R. W. (1967). "Assigning Meanings to Programs." In J. T. Schwartz (Ed.), Mathematical Aspects of Computer Science (Proceedings of Symposia in Applied Mathematics, vol. 19), 19–32. Providence, RI: American Mathematical Society. Introduces the inductive-assertions method for partial correctness and the well-founded-ordering method that converts termination claims into well-founded-descent proofs. registry ↩
[15] Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley. ISBN 9780321573513. Modern treatment pairing algorithmic abstraction with empirical performance measurement on real implementations, addressing the gap between asymptotic elegance and practical executability. registry ↩