34 relations: Binary number, Boolean circuit, Boolean satisfiability problem, Complete (complexity), Computational complexity theory, Context-free grammar, Conway's Game of Life, Decision problem, EXPTIME, Extended Euclidean algorithm, Graph isomorphism, Graph theory, Greatest common divisor, Gzip, Horn clause, Horn-satisfiability, Integer factorization, L (complexity), Lambda calculus, Lempel–Ziv–Welch, Linear programming, Log-space reduction, LZ77 and LZ78, NC (complexity), NP-completeness, P (complexity), Parity game, Reduction (complexity), Sparse language, Time complexity, Turing machine, Type inference, Type theory, Unary numeral system.
In mathematics and digital electronics, a binary number is a number expressed in the base-2 numeral system or binary numeral system, which uses only two symbols: typically 0 (zero) and 1 (one).
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for digital logic circuits.
In computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated as SATISFIABILITY or SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula.
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.
Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.
In formal language theory, a context-free grammar (CFG) is a certain type of formal grammar: a set of production rules that describe all possible strings in a given formal language.
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.
In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that have exponential runtime, i.e., that are solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. In terms of DTIME, We know and also, by the time hierarchy theorem and the space hierarchy theorem, that so at least one of the first three inclusions and at least one of the last three inclusions must be proper, but it is not known which ones are.
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs.
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection.
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.
gzip is a file format and a software application used for file compression and decompression.
In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form which gives it useful properties for use in logic programming, formal specification, and model theory.
In formal logic, Horn-satisfiability, or HORNSAT, is the problem of deciding whether a given set of propositional Horn clauses is satisfiable or not.
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers.
In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space.
Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.
Lempel–Ziv–Welch (LZW) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch.
Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space.
LZ77 and LZ78 are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978.
In 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.
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class.
A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers.
In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem.
In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length n in the language, is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes.
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.
Type inference refers to the automatic detection of the data type of an expression in a programming language.
In mathematics, logic, and computer science, a type theory is any of a class of formal systems, some of which can serve as alternatives to set theory as a foundation for all mathematics.
The unary numeral system is the bijective base-1 numeral system.