P (složitost) - P (complexity)

V teorii výpočetní složitosti je P , také známý jako PTIME nebo DTIME ( n ^{O (1)} ), základní třídou složitosti . Obsahuje všechny rozhodovací problémy, které lze vyřešit deterministickým Turingovým strojem pomocí polynomického množství výpočetního času nebo polynomiálního času .

Cobhamova práce tvrdí, že P je třída výpočetních problémů, které jsou „efektivně řešitelné“ nebo „ traktovatelné “. To je nepřesné: v praxi některé problémy, o nichž není známo, že jsou v P, mají praktická řešení, a některé, které jsou v P, nemají, ale toto je užitečné pravidlo .

Definice

Jazyk L je v P, jestliže a pouze tehdy, když existuje deterministický Turingův stroj M tak, že

• M běží na polynomu na všech vstupech
• Pro všechny výstupy x v L , M 1
• Pro všechny x, které nejsou v L , M výstupy 0

P lze také považovat za jednotnou rodinu booleovských obvodů . Jazyk L je v P právě tehdy, pokud existuje polynomiálně jednotná rodina booleovských obvodů , takže ${\ displaystyle \ {C_ {n}: n \ in \ mathbb {N} \}}$

• Pro všechny , má n bitů jako vstup a výstupy 1 bit${\ Displaystyle n \ in \ mathbb {N}}$${\ displaystyle C_ {n}}$
• Pro všechna x v L ,${\ displaystyle C_ {| x |} (x) = 1}$
• Pro všechna x, která nejsou v L ,${\ displaystyle C_ {| x |} (x) = 0}$

Definici obvodu lze oslabit tak, aby používala pouze uniformní rodinu logspace, aniž by došlo ke změně třídy složitosti.

Významné problémy v P

Je známo, že P obsahuje mnoho přirozených problémů, včetně rozhodovacích verzí lineárního programování a hledání maximální shody . V roce 2002 se ukázalo, že problém určení, zda je číslo prvočíslo, je v P. Související třídou funkčních problémů je FP .

Pro P je dokončeno několik přirozených problémů, včetně st -connectivity (nebo dosažitelnosti ) na střídajících se grafech. Článek o P-úplných problémech uvádí další relevantní problémy v P.

Vztahy k jiným třídám

Zobecnění P ​​je NP , což je třída problémů s rozhodováním, které lze rozhodnout nedeterministickým Turingovým strojem, který běží v polynomiálním čase . Ekvivalentně se jedná o třídu problémů s rozhodováním, kde každá instance „ano“ má certifikát velikosti polynomu a certifikáty lze kontrolovat pomocí polynomiálního časově deterministického Turingova stroje. Třída problémů, pro které to platí pro instance „ne“, se nazývá co-NP . P je triviálně podmnožinou NP a ko-NP; většina odborníků se domnívá, že je to správná podmnožina, ačkoli tato ( hypotéza ) zůstává neprokázaná. Dalším otevřeným problémem je, zda NP = co-NP; protože P = co-P, negativní odpověď by znamenala . ${\ displaystyle {\ mathsf {P}} \ subsetneq {\ mathsf {NP}}}$${\ displaystyle {\ mathsf {P}} \ subsetneq {\ mathsf {NP}}}$

P je také známo, že je alespoň tak velké jako L , což je třída problémů, které lze rozhodnout v logaritmickém množství paměťového prostoru . Rozhodující pomocí mezery nemůže použít více než čas, protože toto je celkový počet možných konfigurací; tedy L je podmnožinou P. Dalším důležitým problémem je, zda L = P. Víme, že P = AL, množina problémů řešitelných v logaritmické paměti střídáním Turingových strojů . P je také známo, že není větší než PSPACE , třída problémů, o nichž lze rozhodnout v polynomiálním prostoru. Opět platí, že zda P = PSPACE je otevřený problém. Shrnout: ${\ displaystyle O (\ log n)}$${\ Displaystyle 2^{O (\ log n)} = n^{O (1)}}$

${\ displaystyle {\ mathsf {L}} \ subseteq {\ mathsf {AL}} = {\ mathsf {P}} \ subseteq {\ mathsf {NP}} \ subseteq {\ mathsf {PSPACE}} \ subseteq {\ mathsf {EXPTIME}}.}$

Zde je EXPTIME třída problémů řešitelných v exponenciálním čase. Ze všech výše uvedených tříd jsou známy pouze dva přísné kontejnery:

• P je přísně obsaženo v EXPTIME. V důsledku toho leží všechny těžké problémy EXPTIME mimo P a alespoň jeden z kontejnmentů napravo od P výše je přísný (ve skutečnosti se všeobecně věří, že všechny tři jsou přísné).
• L je přísně obsaženo v PSPACE.

Nejtěžší problémy v P jsou P-úplné problémy.

Další zobecnění P ​​je P/poly , nebo Nonuniform Polynomial-Time. Pokud je problém v P/poly, pak jej lze vyřešit v deterministickém polynomiálním čase za předpokladu, že je uveden poradní řetězec, který závisí pouze na délce vstupu. Na rozdíl od NP však polynomiální stroj času nemusí detekovat podvodné řetězce doporučení; není to ověřovatel. P/poly je velká třída obsahující téměř všechny praktické problémy, včetně všech BPP . Pokud obsahuje NP, pak se polynomická hierarchie zhroutí na druhou úroveň. Na druhou stranu obsahuje také některé nepraktické problémy, včetně některých nerozhodnutelných problémů , jako je unární verze jakéhokoli nerozhodnutelného problému.

V roce 1999 Jin-Yi Cai a D. Sivakumar, navazující na práci Mitsunori Ogihary , ukázali, že pokud existuje řídký jazyk, který je P-úplný, pak L = P.

Vlastnosti

Algoritmy polynomiálního času jsou uzavřeny pod složením. Intuitivně to říká, že pokud člověk napíše funkci, která je polynomiální, za předpokladu, že volání funkcí jsou konstantní, a pokud tyto volané funkce samy vyžadují polynomický čas, pak celý algoritmus trvá polynomiální čas. Jedním z důsledků toho je, že P je samo o sobě nízké . To je také jeden z hlavních důvodů, proč je P považován za třídu nezávislou na stroji; jakoukoli „funkci“ stroje, jako je náhodný přístup , kterou lze simulovat v polynomiálním čase, lze jednoduše zkombinovat s hlavním algoritmem polynomiálního času a snížit jej tak na algoritmus polynomiálního času na základnějším stroji.

Jazyky v P jsou také uzavřeny pod reverzí, průnikem , sjednocením , zřetězením , Kleeneovým uzavřením , inverzním homomorfismem a komplementací .

Důkazy o čisté existenci polynomiálních časových algoritmů

O některých problémech je známo, že jsou řešitelné v polynomiálním čase, ale není znám žádný konkrétní algoritmus pro jejich řešení. Například Robertsonova – Seymourova věta zaručuje, že existuje konečný seznam zakázaných nezletilých, který charakterizuje (například) sadu grafů, které lze vložit do torusu; navíc Robertson a Seymour ukázali, že existuje algoritmus O ( n ³ ) pro určení, zda graf má daný graf jako vedlejší. To poskytuje nekonstruktivní důkaz, že existuje algoritmus polynomiálního času pro určení, zda daný graf lze vložit do torusu, a to navzdory skutečnosti, že pro tento problém není znám žádný konkrétní algoritmus.

Alternativní charakterizace

V popisné složitosti lze P popsat jako problémy vyjádřitelné v FO (LFP) , logice prvního řádu s přidaným operátorem nejméně pevného bodu , na uspořádaných strukturách. V Immermanově učebnici z roku 1999 o popisné složitosti Immerman připisuje tento výsledek Vardimu a Immermanovi.

V roce 2001 bylo publikováno, že PTIME odpovídá (kladným) gramatikám zřetězení rozsahu .

Dějiny

Kozen uvádí, že Cobhamovi a Edmondsovi „se obecně připisuje vynález pojmu polynomiálního času“. Cobham vynalezl třídu jako robustní způsob charakterizace efektivních algoritmů, což vedlo k Cobhamově tezi . Nicméně, HC Pocklington , v článku z roku 1910, analyzoval dva algoritmy pro řešení kvadratických kongruencí a poznamenal, že jeden potřeboval čas „úměrný mocnině logaritmu modulu“ a porovnal to s tím, který potřeboval čas úměrný „samotnému modulu“ nebo jeho odmocnina “, čímž se výslovně rozlišuje mezi algoritmem, který běžel v polynomiálním čase, a algoritmem, který ne.

Poznámky

Reference

• Cobham, Alan (1965). „Vnitřní výpočetní obtížnost funkcí“. Proč. Logika, metodologie a filozofie vědy II . Severní Holandsko.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest a Clifford Stein . Úvod do algoritmů , druhé vydání. MIT Press a McGraw – Hill, 2001. ISBN  0-262-03293-7 . Oddíl 34.1: Polynomiální čas, s. 971–979.
• Papadimitriou, Christos H. (1994). Výpočetní náročnost . Reading, Mass .: Addison – Wesley. ISBN 978-0-201-53082-7.
• Sipser, Michael (2006). Úvod do teorie výpočtů, 2. vydání . Course Technology Inc. ISBN 978-0-534-95097-2. Oddíl 7.2: Třída P, s. 256–263 ;.

externí odkazy

• Komplexní zoo : Třída P
• Složitost Zoo : Třída P/poly