**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# P (complexity)

Summary

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.
Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or "tractable". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb.
A language L is in P if and only if there exists a deterministic Turing machine M, such that
M runs for polynomial time on all inputs
For all x in L, M outputs 1
For all x not in L, M outputs 0
P can also be viewed as a uniform family of boolean circuits. A language L is in P if and only if there exists a polynomial-time uniform family of boolean circuits , such that
For all , takes n bits as input and outputs 1 bit
For all x in L,
For all x not in L,
The circuit definition can be weakened to use only a logspace uniform family without changing the complexity class.
P is known to contain many natural problems, including the decision versions of linear programming, and finding a maximum matching. In 2002, it was shown that the problem of determining if a number is prime is in P. The related class of function problems is FP.
Several natural problems are complete for P, including st-connectivity (or reachability) on alternating graphs. The article on P-complete problems lists further relevant problems in P.
A generalization of P is NP, which is the class of decision problems decidable by a non-deterministic Turing machine that runs in polynomial time. Equivalently, it is the class of decision problems where each "yes" instance has a polynomial size certificate, and certificates can be checked by a polynomial time deterministic Turing machine. The class of problems for which this is true for the "no" instances is called co-NP.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (12)

Related concepts (43)

Related lectures (127)

CS-524: Computational complexity

In computational complexity we study the computational resources needed to solve problems and understand the relation between different types of computation.
This course advances the students knowle

CS-251: Theory of computation

This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (finite automata, Turing machine), as well as, provides a solid and mathematica

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

Time hierarchy theorem

In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n2 time but not n time. The time hierarchy theorem for deterministic multi-tape Turing machines was first proven by Richard E. Stearns and Juris Hartmanis in 1965. It was improved a year later when F. C. Hennie and Richard E.

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 NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH.

P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or "tractable". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb.

Explores Belief Propagation on trees, discussing cavity marginals, message passing algorithms, and the computation of free entropy.

Covers the design of slides for educational videos and discusses time complexity, diffraction basics, and Shuttle control systems.

Explores dynamic programming through memoization and a bottom-up approach to optimize recursive algorithms.