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 množství času.

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

[editovat] 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].

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

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.

Více o tomto problému najdete v článku Problém P versus NP.

[editovat] 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í.

[editovat] Reference

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