P (třída složitosti)

Z Wikipedie, otevřené encyklopedie

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

Významné problémy v P[editovat | editovat zdroj]

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

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

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

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