Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Download
Faster access than browser!
And Ads-free!

P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is one of the most fundamental complexity classes. [1]

58 relations: Advice (complexity), Alternating Turing machine, Boolean circuit, BPP (complexity), Charles E. Leiserson, Clifford Stein, Co-NP, Cobham's thesis, Complement (complexity), Complexity class, Computational complexity theory, Computational resource, Concatenation, Constructive proof, Decision problem, Descriptive complexity theory, Dexter Kozen, DTIME, EXPTIME, First-order logic, FO (complexity), Forbidden graph characterization, FP (complexity), Function problem, Greatest common divisor, Henry Cabourn Pocklington, Homomorphism, Intersection (set theory), Introduction to Algorithms, Jack Edmonds, Kleene star, L (complexity), Least fixed point, Linear programming, Logarithm, Low (complexity), Matching (graph theory), Non-deterministic Turing machine, NP (complexity), P versus NP problem, P-complete, P/poly, Polynomial, Polynomial hierarchy, Prime number, PSPACE, Random access, Range concatenation grammars, Reachability, Robertson–Seymour theorem, ..., Ron Rivest, Sparse language, St-connectivity, Thomas H. Cormen, Time complexity, Turing machine, Undecidable problem, Union (set theory). Expand index (8 more) »

Advice (complexity)

In computational complexity theory, an advice string is an extra input to a Turing machine which is allowed to depend on the length n of the input, but not on the input itself.

New!!: P (complexity) and Advice (complexity) · See more »

Alternating Turing machine

In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP.

New!!: P (complexity) and Alternating Turing machine · See more »

Boolean circuit

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for digital logic circuits.

New!!: P (complexity) and Boolean circuit · See more »

BPP (complexity)

In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded away from 1/3 for all instances.

New!!: P (complexity) and BPP (complexity) · See more »

Charles E. Leiserson

Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language.

New!!: P (complexity) and Charles E. Leiserson · See more »

Clifford Stein

Clifford Seth Stein (born December 14, 1965), a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Science.

New!!: P (complexity) and Clifford Stein · See more »

Co-NP

In computational complexity theory, co-NP is a complexity class.

New!!: P (complexity) and Co-NP · See more »

Cobham's thesis

Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds), asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P. Formally, to say that a problem can be solved in polynomial time is to say that there exists an algorithm that, given an n-bit instance of the problem as input, can produce a solution in time O(nc), where c is a constant that depends on the problem but not the particular instance of the problem.

New!!: P (complexity) and Cobham's thesis · See more »

Complement (complexity)

In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers.

New!!: P (complexity) and Complement (complexity) · See more »

Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.

New!!: P (complexity) and Complexity class · See more »

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

New!!: P (complexity) and Computational complexity theory · See more »

Computational resource

In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.

New!!: P (complexity) and Computational resource · See more »

Concatenation

In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end.

New!!: P (complexity) and Concatenation · See more »

Constructive proof

In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object.

New!!: P (complexity) and Constructive proof · See more »

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters.

New!!: P (complexity) and Decision problem · See more »

Descriptive complexity theory

Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them.

New!!: P (complexity) and Descriptive complexity theory · See more »

Dexter Kozen

Dexter Campbell Kozen is an American theoretical computer scientist.

New!!: P (complexity) and Dexter Kozen · See more »

DTIME

In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine.

New!!: P (complexity) and DTIME · See more »

EXPTIME

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems 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 (complexity) and EXPTIME · See more »

First-order logic

First-order logic is a formal system used in mathematics, philosophy, linguistics, and computer science.

New!!: P (complexity) and First-order logic · See more »

FO (complexity)

In descriptive complexity, a branch of computational complexity, FO is a complexity class of structures which can be recognized by formulas of first-order logic, and also equals the complexity class AC0.

New!!: P (complexity) and FO (complexity) · See more »

Forbidden graph characterization

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.

New!!: P (complexity) and Forbidden graph characterization · See more »

FP (complexity)

In computational complexity theory, the complexity class FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time; it is the function problem version of the decision problem class P. Roughly speaking, it is the class of functions that can be efficiently computed on classical computers without randomization.

New!!: P (complexity) and FP (complexity) · See more »

Function problem

In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO.

New!!: P (complexity) and Function problem · See more »

Greatest common divisor

In mathematics, the greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder.

New!!: P (complexity) and Greatest common divisor · See more »

Henry Cabourn Pocklington

Henry Cabourn Pocklington FRS (28 January 1870, Exeter – 15 May 1952, Leeds) was an English physicist and mathematician.

New!!: P (complexity) and Henry Cabourn Pocklington · See more »

Homomorphism

In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures (such as groups, rings, or vector spaces).

New!!: P (complexity) and Homomorphism · See more »

Intersection (set theory)

In mathematics, the intersection A ∩ B of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements.

New!!: P (complexity) and Intersection (set theory) · See more »

Introduction to Algorithms

Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

New!!: P (complexity) and Introduction to Algorithms · See more »

Jack Edmonds

Jack R. Edmonds (born April 5, 1934) is an American computer scientist, regarded as one of the most important contributors to the field of combinatorial optimization.

New!!: P (complexity) and Jack Edmonds · See more »

Kleene star

In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters.

New!!: P (complexity) and Kleene star · 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 memory space.

New!!: P (complexity) and L (complexity) · See more »

Least fixed point

In order theory, a branch of mathematics, the least fixed point (lfp or LFP, sometimes also smallest fixed point) of a function from a partially ordered set to itself is the fixed point which is less than each other fixed point, according to the set's order.

New!!: P (complexity) and Least fixed point · 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 (complexity) and Linear programming · See more »

Logarithm

In mathematics, the logarithm is the inverse operation to exponentiation.

New!!: P (complexity) and Logarithm · See more »

Low (complexity)

In computational complexity theory, a complexity class B is said to be low for a complexity class A if AB.

New!!: P (complexity) and Low (complexity) · See more »

Matching (graph theory)

In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices.

New!!: P (complexity) and Matching (graph theory) · See more »

Non-deterministic Turing machine

In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers.

New!!: P (complexity) and Non-deterministic Turing machine · See more »

NP (complexity)

In computational complexity theory, NP is one of the most fundamental complexity classes.

New!!: P (complexity) and NP (complexity) · See more »

P versus NP problem

The P versus NP problem is a major unsolved problem in computer science.

New!!: P (complexity) and P versus NP problem · See more »

P-complete

In complexity theory, the notion of P-complete decision problems is useful in the analysis of both.

New!!: P (complexity) and P-complete · See more »

P/poly

In computational complexity theory, P/poly is the complexity class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function.

New!!: P (complexity) and P/poly · See more »

Polynomial

In mathematics, a polynomial is an expression consisting of variables (or indeterminates) and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents.

New!!: P (complexity) and Polynomial · See more »

Polynomial hierarchy

In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.

New!!: P (complexity) and Polynomial hierarchy · See more »

Prime number

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

New!!: P (complexity) and Prime number · See more »

PSPACE

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

New!!: P (complexity) and PSPACE · See more »

Random access

In computer science, random access (more precisely and more generally called direct access) is the ability to access an item of data at any given coordinates in a population of addressable elements.

New!!: P (complexity) and Random access · See more »

Range concatenation grammars

Range concatenation grammar (RCG) is a grammar formalism developed by Pierre Boullier in 1998 as an attempt to characterize a number of phenomena of natural language, such as Chinese numbers and German word order scrambling, which are outside the bounds of the Mildly context-sensitive languages.

New!!: P (complexity) and Range concatenation grammars · See more »

Reachability

In graph theory, reachability refers to the ability to get from one vertex to another within a graph.

New!!: P (complexity) and Reachability · See more »

Robertson–Seymour theorem

In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering.

New!!: P (complexity) and Robertson–Seymour theorem · See more »

Ron Rivest

Ronald Linn Rivest (born May 6, 1947) is a cryptographer and an Institute Professor at MIT.

New!!: P (complexity) and Ron Rivest · 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 (complexity) and Sparse language · See more »

St-connectivity

In computer science and computational complexity theory, st-connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s. Formally, the decision problem is given by.

New!!: P (complexity) and St-connectivity · See more »

Thomas H. Cormen

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein.

New!!: P (complexity) and Thomas H. Cormen · See more »

Time complexity

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

New!!: P (complexity) and Time complexity · See more »

Turing machine

A Turing machine is an abstract "machine" that manipulates symbols on a strip of tape according to a table of rules; to be more exact, it is a mathematical model that defines such a device.

New!!: P (complexity) and Turing machine · See more »

Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer.

New!!: P (complexity) and Undecidable problem · See more »

Union (set theory)

In set theory, the union (denoted by ∪) of a collection of sets is the set of all distinct elements in the collection.

New!!: P (complexity) and Union (set theory) · See more »

References

[1] https://en.wikipedia.org/wiki/P_(complexity)

OutgoingIncoming
Hey! We are on Facebook now! »