P (třída složitosti)
třída složitosti From Wikipedia, the free encyclopedia
třída složitosti From Wikipedia, the free encyclopedia
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).
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].
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.
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í.