Třída P

V teorii algoritmů je třída P (z anglického  polynomial ) souborem problémů, pro které existují „rychlé“ algoritmy řešení (jejichž doba běhu závisí polynomiálně na velikosti vstupních dat). Třída P je součástí širších tříd složitosti algoritmů.

Definice

Formální definice

Algoritmus je identifikován s deterministickým Turingovým strojem , který vypočítává odpověď dané slovem ze vstupní abecedy dané vstupní pásce . Doba běhu algoritmu pro pevné vstupní slovo x je počet pracovních cyklů Turingova stroje od spuštění do zastavení stroje. Složitost funkce vypočítaná nějakým Turingovým strojem je funkce , která závisí na délce vstupního slova a rovná se maximální době běhu stroje přes všechna vstupní slova pevné délky:

Jestliže pro funkci f existuje Turingův stroj M takový, že pro nějaké číslo c a dostatečně velké n , pak se říká, že patří do třídy P nebo je polynomiální v čase.

Podle Church-Turingovy teze lze na Turingově stroji implementovat jakýkoli myslitelný algoritmus. Pro jakýkoli programovací jazyk můžete definovat třídu P podobným způsobem (nahrazení Turingova stroje v definici implementací programovacího jazyka). Pokud kompilátor jazyka, ve kterém je algoritmus implementován, zpomalí provádění algoritmu polynomiálně (to znamená, že doba provádění algoritmu na Turingově stroji je kratší než nějaký polynom jeho doby provádění v programovacím jazyce), pak definice tříd P pro tento jazyk a pro Turingův stroj jsou stejné. Kód assembleru lze převést na Turingův stroj s malým polynomiálním zpomalením, a protože všechny existující jazyky umožňují kompilaci do sestavení (opět s polynomiálním zpomalením), definice třídy P pro Turingovy stroje a pro jakýkoli existující programovací jazyk jsou stejní.

Užší definice

Někdy třída P znamená užší třídu funkcí, konkrétně třídu predikátů (funkcí ). V tomto případě jazyk L , který je rozpoznán tímto predikátem, je množina slov, na kterých je predikát roven 1. Jazyky třídy P jsou jazyky, pro které existují predikáty třídy P, které je rozpoznávají. Je zřejmé, že pokud jazyky a leží ve třídě P, pak jejich sjednocení, průnik a doplňky také patří do třídy P.

Zařazení třídy P do jiných tříd

Třída P je jednou z nejužších tříd složitosti. Algoritmy, které mu patří, také patří do třídy NP , třídy BPP (protože umožňují implementaci polynomu s nulovou chybou), třídy PSPACE (protože oblast práce na Turingově stroji je vždy menší než čas), třída P/Poly (k prokázání této skutečnosti je použit koncept protokolu stroje, který je převeden na booleovské schéma polynomiální velikosti).

Již více než 30 let zůstává problém rovnosti tříd P a NP nevyřešen . Pokud se rovnají, pak lze jakýkoli problém z třídy NP vyřešit rychle (v polynomiálním čase). Vědecká komunita se však přiklání k negativní odpovědi na tuto otázku. Navíc není prokázána přísnost zařazení do širších tříd např. v PSPACE, ale rovnost P a PSPACE vypadá v tuto chvíli velmi pochybně.

Příklady problémů

Problémy patřící do třídy P

Příklady problémů ze třídy P jsou sčítání celých čísel, násobení, dělení, přijímání zbytku dělení, násobení matic , zjišťování spojitosti grafů , řazení množiny n čísel, hledání Eulerova cyklu na grafu o m hranách, hledání některých slovo v textu délky n, konstrukce pokrývajících stromů minimálních nákladů, lineární programování a některé další.

Problémy, jejichž členství ve třídě P je neznámé

Existuje mnoho problémů, pro které nebyl nalezen žádný polynomiální algoritmus, ale nebylo prokázáno, že neexistuje. Není tedy známo, zda takové problémy patří do třídy P. Zde jsou některé z nich:

1. Problém cestujícího prodejce (stejně jako všechny ostatní NP-úplné problémy ). Polynomiální řešení tohoto problému je ekvivalentní stanovení rovnosti tříd P a NP .
2. Rozklad čísla na prvočinitele .
3. Diskrétní logaritmus v konečném poli .
4. Problém skryté podskupiny s n generátory.
5. Diskrétní logaritmus v aditivní skupině bodů na eliptické křivce .

Praktická hodnota

Protože je často nutné počítat hodnoty funkcí na velkých vstupních datech, je nalezení polynomiálních algoritmů pro výpočet funkcí velmi důležitým úkolem. Předpokládá se, že je mnohem obtížnější vypočítat funkce, které nepatří do třídy P, než ty, které do třídy P patří. Většina algoritmů ve třídě P má složitost, která nepřesahuje polynom malého stupně velikosti vstupních dat. Například standardní maticový násobící algoritmus vyžaduje n 3 násobení (ačkoli existují rychlejší algoritmy, jako je Strassenův algoritmus ). Stupeň polynomu je zřídka velký. Jedním z takových případů je test Agrawal-Kayala-Saksena navržený v roce 2002 indickými matematiky , který zjišťuje, zda je číslo n prvočíslo v operacích O (log 6 n ).

Literatura

• Thomas H. Kormen a kol. , Algoritmy: Konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - M .: "Williams" , 2006. - 1296 s. — ISBN 0-07-013151-1 .
• John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Úvod do teorie automatů, jazyků a počítání. - M .: "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .

Odkazy