P (complexity)

In complexity theory, P ( also: PTIME ) that complexity class that contains all decision problems that are solvable in polynomial time deterministic Turing machines. This class of problems is generally regarded as the class of " practical detachable " problems.

A generalization of P is the class NP. Although the problems of NP are also decidable in polynomial time, but you need a non- viable, namely non-deterministic machine model is used. P is definitely a subset of NP. However, it is one of the most important unsolved problems in theoretical computer science, if P = NP (see also P- NP problem ).

Relation to other complexity classes

The following relations are known:

P- completeness

A decision problem is called P -complete if and only if it lies in the complexity class P, and if any problem can be reduced in P by a computation with logarithmic space consumption, 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 in which is to be determined whether the result of a Boolean circuit for a given input to a given output matches. These problems are among the most difficult, yet efficiently solvable problems in the complexity class P. P- complete problems are ( currently ) hard to parallelize.

Known Issues in P

  • PRIMES

P- complete problems

  • Linear Programming
  • Circuit Value Problem
  • HORNSAT
Recursive set Time complexity#Polynomial time Nondeterministic algorithm EXPTIME NEXPTIME Primality test
483689
de