Computation Models & Complexity Classes¶

← Back to Domain-Specific Families

Abstractions that formalize computation and its cost, spanning abstract machine models (Mealy machines, counter machines, Boolean circuits), complexity-class hierarchies (NC, NE, FPT, co-RE-complete), and programming-language mechanisms (coroutines, subtyping, opaque data types, parameterized macros).

37 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

Analysis of algorithms — In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them.
Automatic parallelization — Automatic parallelization, also auto-parallelization or autoparallelization, is a compiler optimization in which a compiler or other software tool transforms sequential program code so that some of its operations can execute in parallel.
Boolean circuit — In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits.
Busy beaver — The n-state busy beaver game consists of finding the longest-running or highest-scoring Turing machine which has n states and eventually halts.
Co-RE-complete — A decision problem is co-RE-complete when it belongs to co-RE and every problem in co-RE reduces to it under the declared reduction, making it maximally hard within that class.
Co-simulation — In co-simulation, the different subsystems that form a coupled problem are modeled and simulated in a distributed manner.
Compiler correctness — In computing, compiler correctness is the branch of computer science that deals with trying to show that a compiler behaves according to its language specification.
Complete (complexity) — In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class.
Configuration Graph — Configuration graphs are a theoretical tool used in computational complexity theory to prove a relation between graph reachability and complexity classes.
Coroutines — Coroutines are computer program components that can be suspended and resumed — generalizing subroutines — for cooperative multitasking.
Counter-machine model — A counter-machine model is an abstract machine with finite-state control and integer counters that instructions increment, decrement, test, and branch upon to model computation.
Denotational semantics of the Actor model — The denotational semantics of the Actor model is the subject of denotational domain theory for Actors.
FPT (complexity class) — A parameterized problem that allows for such an FPT algorithm is said to be a fixed-parameter tractable problem and belongs to the class , and the early name of the theory of parameterized complexity was fixed-parameter tractability.
Function call — In computer programming, a function (also procedure, method, subroutine, routine, or subprogram) is a callable unit of software logic that has a well-formed interface and behavior and can be invoked multiple times.
Functional reactive programming — Functional reactive programming (FRP) is a programming paradigm for reactive programming (asynchronous dataflow programming) using the building blocks of functional programming (e.g., map, reduce, filter).
Generator matrix — In coding theory, a generator matrix is a matrix whose rows form a basis for a linear code.
High (computability) — In computability theory, a Turing degree [X] is high if it is computable in 0, and the Turing jump ['] is 0, which is the greatest possible degree in terms of Turing reducibility for the jump of a set which is computable in 0.
Integer Overflow — The failure mode where an arithmetic result exceeds a fixed-width integer field's range and the runtime silently writes back a wrapped value with no trap or flag — so downstream code trusts a number that is no longer what the computation demanded.
Mealy machine — In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs.
Multi-stage programming — Multi-stage programming (MSP) is a variety of metaprogramming in which compilation is divided into a series of intermediate phases, allowing typesafe run-time code generation.
Natural-Language Programming — Natural language programming (NLP) is an ontology-assisted way of programming in terms of natural language sentences, e.g.
NC (complexity) — In computational complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors.
NE (complexity) — In computational complexity theory, the complexity class NE is the set of decision problems that can be solved by a non-deterministic Turing machine in time 2^{O(n)}.
Nets-Within-Nets — Nets within nets is a modelling method belonging to the family of Petri nets.
Opaque data type — In computer science, an opaque data type is a data type whose concrete data structure is not defined in an interface.
Parallel computation thesis — In computational complexity theory, the parallel computation thesis is a hypothesis which states that the time used by a (reasonable) parallel machine is polynomially related to the space used by a sequential machine.
Parameterized Macro — A parameterized macro (or function-like macro) is a macro that is able to insert given objects into its expansion.
Quantum Byzantine Agreement — This shows that the quantum implementation of classical Byzantine Agreement protocols is indeed feasible.
Randomness extractor — A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weak entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed.
Rational data type — Haskell provides a type, which is really an alias for ( being a polymorphic type implementing rational numbers for any type of numerators and denominators).
Scoreboarding — Scoreboarding is a centralized method, first used in the CDC 6600 computer, for dynamically scheduling instructions so that they can execute out of order when there are no conflicts and the hardware is available.
Shelving buffer — A shelving buffer is a technique used in computer processors to increase the efficiency of superscalar processors.
Stream X-Machine — The Stream X-machine (SXM) is a model of computation introduced by Gilbert Laycock in his 1993 PhD thesis, The Theory and Practice of Specification Based Software Testing.
Subtyping — In programming language theory, subtyping (also called subtype polymorphism or inclusion polymorphism) is a form of type polymorphism.
Transdichotomous model — In computational complexity theory, and more specifically in the analysis of algorithms with integer data, the transdichotomous model is a variation of the random-access machine in which the machine word size is assumed to match the problem size.
Typing Environment — In statically typed programming languages, these environments are used and maintained by typing rules to type check a given program or expression.
Unambiguous finite automaton — In automata theory, an unambiguous finite automaton (UFA) is a nondeterministic finite automaton (NFA) such that each word has at most one accepting path.