Mathematics and statistics

Subset sum problem

The subset sum problem asks whether some subset of a set of integers sums exactly to a target. It was proved NP-complete in Richard Karp's 1972 paper.

Subshift of finite type

A subshift of finite type, also called a Markov shift, is a set of infinite sequences avoiding a finite list of forbidden words, central to symbolic dynamics.

The Subspace theorem is a 1972 result of Wolfgang M. Schmidt in Diophantine approximation, generalizing Roth's theorem: solutions of a product inequality in linear forms lie in finitely many subspaces.

Subspace topology

The subspace topology, also called the induced or relative topology, is the topology on a subset A of a space X whose open sets are the intersections U ∩ A.

Substitution cipher

A substitution cipher, also called a simple or monoalphabetic substitution cipher, is an encryption method replacing each plaintext letter by another symbol according to a fixed key.

Substring

A substring, also known as a subword or factor, is a contiguous sequence of characters taken from within a longer string; unlike a subsequence, it must occupy consecutive positions.

Substructural logic

Substructural logic is a family of non-classical logics lacking one or more structural rules of classical logic, including relevant logics, the Lambek calculus, and linear logic.

Substructural type system

A substructural type system removes one or more structural rules, such as weakening or contraction, so the type system controls whether variables can be reordered, discarded, or duplicated.

Subtraction

Subtraction is one of the four basic arithmetic operations, written with the minus sign (−) as minuend − subtrahend = difference, as in 7 − 4 = 3.

Successive over-relaxation

Successive over-relaxation (SOR) is an iterative method for solving linear systems, using a relaxation factor to speed up Gauss–Seidel, especially for sparse systems from discretized PDEs.

Sufficient dimension reduction

Sufficient dimension reduction (SDR) is a family of statistical methods that replaces a predictor vector with a few linear combinations retaining all information about the response.

Sufficient statistic

A sufficient statistic is a function of a sample holding all the information the data provide about a model's parameters, introduced by Ronald A. Fisher in 1922.

Suffix tree

The suffix tree, also called a position tree, is a compressed trie containing all suffixes of a text, allowing substring queries in time linear in the pattern length.

Sugeno integral

The Sugeno integral is a nonlinear aggregation operator that combines values with respect to a fuzzy measure, using only maximum and minimum instead of addition and multiplication.

SuiteSparse

SuiteSparse is an open-source collection of sparse matrix algorithm packages written or co-authored by Timothy A. Davis of Texas A&M University, providing solvers used in MATLAB, Julia, and Google Earth.

Sum of angles of a triangle

The sum of angles of a triangle, also known as the angle sum of a triangle, equals 180° in Euclidean plane geometry, stated in Euclid's Elements.

Sum of normally distributed random variables

The sum of normally distributed random variables is itself normally distributed whenever the summands are independent: means add, variances add, and the property extends to any linear combination.

Sum of squares

A sum of squares is an expression in which squared quantities are added, naming ideas in number theory, statistics, and optimization that exploit squares never being negative.

Sum-free set

A sum-free set is a set of numbers containing no solution of x + y = z with all three terms in the set, arising from Schur's 1916 work.

Sum-of-squares proof

A sum-of-squares proof is a certificate that a polynomial is nonnegative, given by writing it as a sum of squares of polynomials, testable efficiently through semidefinite programming.

Summation

Summation is the operation of adding a sequence of numbers or terms to produce a total called a sum, written compactly with sigma notation introduced by Euler in 1755.

Summation by parts

Summation by parts (SBP) is a discrete analog of integration by parts: identities and finite-difference operators that shift a difference between factors, leaving boundary terms, used to prove stability.

Sums of powers

Sums of powers, also called power sums, are expressions writing a positive integer as a sum of k-th powers of integers, central to Waring's problem and Faulhaber's formula.

Super vector space

A super vector space is a vector space split into an even and an odd part, where exchanging two odd factors in a tensor product introduces a minus sign.

Super-recursive algorithm

A super-recursive algorithm is, in Mark Burgin's classification of algorithmic models, a model of computation exceeding Turing machines, exemplified by inductive Turing machines that produce results by output stabilizing.

Supercompact cardinal

A supercompact cardinal is a large cardinal in set theory defined by Reinhardt and Solovay around 1968, much stronger than measurability and stronger than every Woodin cardinal.

Superior highly composite number

A superior highly composite number is an integer that maximizes the divisor-count ratio d(n)/n^ε for some ε, introduced by Srinivasa Ramanujan in his 1915 memoir on highly composite numbers.

Supermartingale

A supermartingale is a stochastic process whose expected future value, conditional on everything known so far, is never greater than its present value, as in an unfavorable game.

Superpermutation

A superpermutation is a string over n symbols that contains every one of the n! permutations as a contiguous substring; the minimum length remains open for n at least 6.