Algorithms, Proofs & Computational Decisions

← Back to Domain-Specific Families

Abstractions about computational problems solved through algorithms, reductions, search, matching, hashing, and interactive proof. They also cover authentication assumptions, regret and decision principles, complexity bounds, witness structures, and distributed coordination procedures.

25 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.

• Argumentation framework — A formal model representing arguments and attack relations so admissible, preferred, stable or grounded sets of jointly defensible arguments can be computed.
• Biba Model — A mandatory access-control integrity model that orders subjects and objects by integrity level and restricts information flow to prevent lower-integrity data from contaminating higher-integrity state.
• Boy or girl paradox — A probability puzzle showing that conditioning on family sex composition depends on how the information was selected and reported.
• Bully algorithm — A distributed leader-election algorithm in which the highest-identifier live process eventually becomes coordinator after failures.
• Competitive regret — An online-learning performance measure comparing an algorithm's regret with that of a stronger oracle or benchmark that may possess additional information or computational capability.
• Computational problem — A formally specified relation between encoded instances and acceptable solutions sought by an algorithm.
• Decisional Diffie–Hellman assumption — The cryptographic hardness assumption that a genuine Diffie–Hellman tuple is computationally indistinguishable from one with an independent random final group element.
• Hi/Lo algorithm — A distributed identifier-allocation strategy that reserves a high-value block centrally and generates low values locally within that block.
• Incompressibility method — A proof method that selects a Kolmogorov-incompressible object and shows that failure of the desired property would yield an impossibly shorter description.
• Interactive proof system — A protocol in which a computationally unbounded but untrusted prover exchanges messages with a resource-bounded randomized verifier to establish language membership with completeness and soundness guarantees.
• Locality-sensitive hashing — A randomized indexing method using hash families whose collision probability increases with similarity under a target distance measure.
• MAX-3SAT — The optimization problem of assigning truth values to maximize the number or weight of satisfied clauses in a Boolean formula with at most three literals per clause.
• Merge algorithm — An algorithm that combines multiple already-sorted input sequences into one sorted output while preserving every input element and the declared ordering policy.
• Metapattern — A recurring organization among patterns themselves—a higher-order pattern that connects, transforms or generates patterns across instances or domains.
• Multi-factor authentication — Authentication requiring evidence from at least two independent factor categories such as knowledge, possession, and inherence before granting access.
• Nearest neighbor search — The optimization problem of finding dataset items minimizing a specified distance or dissimilarity to a query.
• Partial sorting — Rearrangement that places the k smallest or largest elements in their fully sorted positions while leaving or discarding the remainder without requiring a total order output.
• Passwordless authentication — Authentication that verifies a claimant without requiring entry of a memorized knowledge secret, usually through a registered device, cryptographic key or inherence factor.
• Pignistic probability — A decision probability obtained from a belief function by distributing each focal set's mass equally among its members when a single probabilistic choice is required.
• Qualification problem — The knowledge-representation problem that real-world actions have indefinitely many exceptional preconditions, making a complete list of conditions for their intended effects impossible to state in advance.
• Reduction (complexity) — An algorithmic transformation from instances of one computational problem to another that preserves answers and is efficient enough to transfer solvability or hardness results.
• Relational transducer — A state-machine model whose input, output, memory and transition state are finite relational database instances transformed by declarative queries.
• Stable matching problem — The problem of pairing members of two preference-bearing sets so that no unmatched pair would both prefer each other to their assigned partners.
• Sure-thing principle — A decision principle requiring the same action when it is preferred both conditional on an event and conditional on its complement.
• Witness set — A set of input points whose labeled values distinguish one Boolean function or concept from every rival in a declared class.