P (complexity class)

In complexity theory , P (also: PTIME ) is the complexity class that contains all decision problems that can be solved in polynomial time for deterministic Turing machines . This class of problems is generally considered to be the class of "practically solvable" problems.

A generalization of P is the class NP . The problems from NP can also be decided in polynomial time, but a non-realizable, namely nondeterministic machine model is used for this. P is certainly a subset of NP. However, one of the most important unsolved questions in theoretical computer science is whether P = NP holds ( see also P-NP problem ).

P is closed with a complement.

Relationship to other complexity classes

The following relationships are known:

L ⊆ NL ⊆ LOGCFL ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE = NEXPSPACE

LOGCFL PSPACE EXPSPACE

{\ displaystyle \ not =}

{\ displaystyle \ not =}

P EXPTIME

{\ displaystyle \ not =}

P-completeness

A decision problem is called P-full if and only if it is in the complexity class is P and when any problem in P by a calculation with logarithmic space consumption to be reduced, that is, if each of these reductions in the complexity class L is ( see also: completeness in complexity theory ). ${\ displaystyle A}$ ${\ displaystyle A}$

A well-known P-complete problem is the circuit value problem , the purpose of which is to determine whether the result of a Boolean circuit given an input corresponds to a given output. These problems belong to the most difficult, still efficiently solvable problems from the complexity class P. P-complete problems are (at the moment) difficult to parallelize.

Known issues in P

A great many problems lie in P, which is generally not particularly noticed; As a rule, a suitable algorithm is then also known (such as the sorting problem with e.g. quicksort , runtime , etc.). ${\ displaystyle {\ mathcal {O}} (n ^ {2})}$

PRIMES is a problem that, contrary to many earlier assumptions, is in P ( AKS prime number test , 2002)

P-complete problems

Web links

P . In: Complexity Zoo. (English)
A Compendium of problem Complete for P (English)