P (complexity class)

from Wikipedia, the free encyclopedia

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:



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 ).

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.).

P-complete problems

Web links