In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, P, also known as PTIME or
DTIME In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would ta ...
(''n''
O(1)), is a fundamental
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...
. It contains all
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
s that can be solved by a
deterministic Turing machine using a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
amount of
computation time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
, 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.
Definition
A
language
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of ...
''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 circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inp ...
s. 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.
Notable problems in P
P is known to contain many natural problems, including the decision versions of
linear programming, and finding a
maximum matching
Maximum cardinality matching is a fundamental problem in graph theory.
We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adj ...
. In 2002, it was shown that the problem of determining if a number is
prime
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
is in P. The related class of
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. For function problems, the o ...
s is
FP.
Several natural problems are complete for P, including
''st''-connectivity (or
reachability
In graph theory, reachability refers to the ability to get from one Vertex (graph theory), vertex to another within a graph. A vertex s can reach a vertex t (and t is reachable from s) if there exists a sequence of Glossary of graph theory#Basics, ...
) on alternating graphs.
The article on
P-complete problems lists further relevant problems in P.
Relationships to other classes
A generalization of P is
NP, which is the class of
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
s decidable by a
non-deterministic Turing machine
In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...
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
In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely ...
. P is trivially a subset of NP and of co-NP; most experts believe it is a proper subset, although this belief (the
hypothesis)
remains unproven. Another open problem is whether NP = co-NP; since P = co-P, a negative answer would imply
.
P is also known to be at least as large as
L, the class of problems decidable in a
logarithm
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 of ...
ic amount of
memory space. A decider using
space cannot use more than
time, because this is the total number of possible configurations; thus, L is a subset of P. Another important problem is whether L = P. We do know that P = AL, the set of problems solvable in logarithmic memory by
alternating Turing machines. P is also known to be no larger than
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.
Formal definition
If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...
, the class of problems decidable in polynomial space. Again, whether P = PSPACE is an open problem. To summarize:
:
Here,
EXPTIME is the class of problems solvable in exponential time. Of all the classes shown above, only two strict containments are known:
* P is strictly contained in EXPTIME. Consequently, all EXPTIME-hard problems lie outside P, and at least one of the containments to the right of P above is strict (in fact, it is widely believed that all three are strict).
* L is strictly contained in PSPACE.
The most difficult problems in P are
P-complete In computational complexity theory, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction.
The notion of P-complete decision problems is usef ...
problems.
Another generalization of P is
P/poly
In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. It can also be defined equiva ...
, or Nonuniform Polynomial-Time. If a problem is in P/poly, then it can be solved in deterministic polynomial time provided that an
advice string is given that depends only on the length of the input. Unlike for NP, however, the polynomial-time machine doesn't need to detect fraudulent advice strings; it is not a verifier. P/poly is a large class containing nearly all practical problems, including all of
BPP
BPP may refer to:
Education
* BPP Holdings, a holding company based in the United Kingdom
* BPP Law School, a law school based in the United Kingdom and a constituent school of BPP University
* BPP University, a private university based in the ...
. If it contains NP, then the
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. ...
collapses to the second level. On the other hand, it also contains some impractical problems, including some
undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an ...
s such as the unary version of any undecidable problem.
In 1999, Jin-Yi Cai and D. Sivakumar, building on work by
Mitsunori Ogihara, showed that if there exists a
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 ...
that is P-complete, then L = P.
Properties
Polynomial-time algorithms are closed under composition. Intuitively, this says that if one writes a function that is polynomial-time assuming that function calls are constant-time, and if those called functions themselves require polynomial time, then the entire algorithm takes polynomial time. One consequence of this is that P is
low for itself. This is also one of the main reasons that P is considered to be a machine-independent class; any machine "feature", such as
random access, that can be simulated in polynomial time can simply be composed with the main polynomial-time algorithm to reduce it to a polynomial-time algorithm on a more basic machine.
Languages in P are also closed under reversal,
intersection,
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
,
concatenation
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalisations of concatenat ...
,
Kleene closure
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. In mathematics,
it is more commonly known as the free monoid ...
, inverse
homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
, and
complementation.
Pure existence proofs of polynomial-time algorithms
Some problems are known to be solvable in polynomial time, but no concrete algorithm is known for solving them. For example, the
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. Equivalently, every family of graphs that is c ...
guarantees that there is a finite list of
forbidden minor
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 forbidde ...
s that characterizes (for example) the set of graphs that can be embedded on a torus; moreover, Robertson and Seymour showed that there is an O(''n''
3) algorithm for determining whether a graph has a given graph as a minor. This yields a
nonconstructive 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. This is in contrast to a non-constructive proof (also known as an existenc ...
that there is a polynomial-time algorithm for determining if a given graph can be embedded on a torus, despite the fact that no concrete algorithm is known for this problem.
Alternative characterizations
In
descriptive complexity
''Descriptive Complexity'' is a book in mathematical logic and computational complexity theory by Neil Immerman. It concerns descriptive complexity theory, an area in which the expressibility of mathematical properties using different types of lo ...
, P can be described as the problems expressible in
FO(LFP), the
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
with a
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 ...
operator added to it, on ordered structures. In Immerman's
1999 textbook on descriptive complexity, Immerman ascribes this result to Vardi and to Immerman.
It was published in 2001 that PTIME corresponds to (positive)
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 b ...
.
[ citing http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf for the proof]
P can also be defined as an algorithmic complexity class for problems that are not decision problems
(even though, for example, finding the solution to a
2-satisfiability
In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case ...
instance in polynomial time automatically gives a polynomial algorithm for the corresponding decision problem). In that case P is not a subset of NP, but P∩DEC is, where DEC is the class of decision problems.
History
Kozen states that
Cobham and
Edmonds Edmonds may refer to:
* Edmonds (surname), a surname (including a list of people with the surname)
* Edmonds, Washington, a city in Washington, US
** Edmonds station (Washington), a passenger train station in Washington, US
* Edmonds station (SkyTr ...
are "generally credited with the invention of the notion of polynomial time." Cobham invented the class as a robust way of characterizing efficient algorithms, leading to
Cobham's thesis. However,
H. C. Pocklington, in a 1910 paper,
analyzed two algorithms for solving quadratic congruences, and observed that one took time "proportional to a power of the logarithm of the modulus" and contrasted this with one that took time proportional "to the modulus itself or its square root", thus explicitly drawing a distinction between an algorithm that ran in polynomial time versus one that did not.
Notes
References
*
*
Thomas H. Cormen
Thomas H. Cormen is the co-author of ''Introduction to Algorithms'', along with Charles Leiserson, Ron Rivest, and Cliff Stein. In 2013, he published a new book titled '' Algorithms Unlocked''. He is a professor of computer science at Dartmout ...
,
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. ...
,
Ronald L. Rivest
Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Inte ...
, and
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 Scien ...
. ''
Introduction to Algorithms
''Introduction to Algorithms'' is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The book has been widely used as the textbook for algorithms courses at many universities and is ...
'', Second Edition. MIT Press and McGraw–Hill, 2001. . Section 34.1: Polynomial time, pp. 971–979.
*
* Section 7.2: The Class P, pp. 256–263;.
External links
*
*
{{ComplexityClasses
Complexity classes