P (třída složitosti)

V teorii složitosti je P jednou z nejzákladnějších tříd složitosti. Obsahuje všechny problémy řešitelné pomocí deterministického Turingova stroje v polynomiálním čase.

P je obvykle považována za třídu problémů, které jsou efektivně řešitelné (existují ale i další třídy považované za efektivně řešitelné, jako RP a BPP), přesto není v této třídě problém najít i efektivně neřešitelné problémy (se složitostí například N^1000000).

Významné problémy v P

P obsahuje velké množství přirozených problémů, včetně počítání největšího společného dělitele nebo nalezení maximálního párování grafu. V roce 2002 bylo dokázáno, že problém rozhodnutí prvočíselnosti leží v třídě P^[1].

Vztah k dalším složitostním třídám

Podrobnější informace naleznete v článku Problém P versus NP.

Zobecnění (nadmnožina) P je NP, což je třída problémů rozhodnutelných v polynomiálním čase na nedeterministickém Turingově stroji. Vztah tříd P a NP není dosud vyřešen, je možné, že se tyto třídy rovnají. Přestože důkaz zatím neexistuje, většina expertů věří, že P je vlastní podmnožinou NP.

Vlastnosti

Polynomiální algoritmy jsou uzavřené na skládání. Tzn. uvažujme funkci, která běží v polynomiálním čase. Nahraďme volání libovolných konstantních funkcí voláními funkcí běžících v polynomiálním čase. Pak je i tato pozměněná funkce polynomiální.

Reference

1. Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.