# 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:

LNLLOGCFLNC ⊆ P ⊆ NPPSPACE = NPSPACE ⊆ EXPTIMENEXPTIMEEXPSPACE = 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})}$