Faster access than browser!
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.
Binary number
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).
New!!: P-complete and Binary number · See more »
Boolean circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for digital logic circuits.
New!!: P-complete and Boolean circuit · See more »
Boolean satisfiability problem
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.
New!!: P-complete and Boolean satisfiability problem · See more »
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.
New!!: P-complete and Complete (complexity) · See more »
Computational complexity theory
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.
New!!: P-complete and Computational complexity theory · See more »
Context-free grammar
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.
New!!: P-complete and Context-free grammar · See more »
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.
New!!: P-complete and Conway's Game of Life · See more »
Decision problem
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.
New!!: P-complete and Decision problem · See more »
EXPTIME
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.
New!!: P-complete and EXPTIME · See more »
Extended Euclidean algorithm
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.
New!!: P-complete and Extended Euclidean algorithm · See more »
Graph isomorphism
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.
New!!: P-complete and Graph isomorphism · See more »
Graph theory
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
New!!: P-complete and Graph theory · See more »
Greatest common divisor
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.
New!!: P-complete and Greatest common divisor · See more »
Gzip
gzip is a file format and a software application used for file compression and decompression.
New!!: P-complete and Gzip · See more »
Horn clause
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.
New!!: P-complete and Horn clause · See more »
Horn-satisfiability
In formal logic, Horn-satisfiability, or HORNSAT, is the problem of deciding whether a given set of propositional Horn clauses is satisfiable or not.
New!!: P-complete and Horn-satisfiability · See more »
Integer factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers.
New!!: P-complete and Integer factorization · See more »
L (complexity)
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.
New!!: P-complete and L (complexity) · See more »
Lambda calculus
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.
New!!: P-complete and Lambda calculus · See more »
Lempel–Ziv–Welch
Lempel–Ziv–Welch (LZW) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch.
New!!: P-complete and Lempel–Ziv–Welch · See more »
Linear programming
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.
New!!: P-complete and Linear programming · See more »
Log-space reduction
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space.
New!!: P-complete and Log-space reduction · See more »
LZ77 and LZ78
LZ77 and LZ78 are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978.
New!!: P-complete and LZ77 and LZ78 · See more »
NC (complexity)
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.
New!!: P-complete and NC (complexity) · See more »
NP-completeness
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
New!!: P-complete and NP-completeness · See more »
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class.
New!!: P-complete and P (complexity) · See more »
Parity game
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.
New!!: P-complete and Parity game · See more »
Reduction (complexity)
In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem.
New!!: P-complete and Reduction (complexity) · See more »
Sparse language
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.
New!!: P-complete and Sparse language · See more »
Time complexity
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
New!!: P-complete and Time complexity · See more »
Turing machine
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.
New!!: P-complete and Turing machine · See more »
Type inference
Type inference refers to the automatic detection of the data type of an expression in a programming language.
New!!: P-complete and Type inference · See more »
Type theory
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.
New!!: P-complete and Type theory · See more »
Unary numeral system
The unary numeral system is the bijective base-1 numeral system.
New!!: P-complete and Unary numeral system · See more »
Redirects here:
Circuit value problem, P complete, P-Complete, PTIME-complete, PTIME-hard.
References
[1] https://en.wikipedia.org/wiki/P-complete
