ARTP - 12 - Zložitostné triedy pravdepodobnostných algoritmov

Zhrnutie prednášky

Prednáška zaraďuje triedy zložitosti pravdepodobnostných algoritmov do známej hierarchie rozhodovacích problémov. Najprv pripomína triedy P a NP, vysvetľuje nedeterministické výpočty ako vetvenie s orákulom hľadajúcim najkratšiu cestu k odpovedi áno a definuje triedu coNP, kde sa hľadá najkratšia cesta k odpovedi nie. Potom zavádza triedu RP jednostranných Monte Carlo algoritmov, ktoré pri správnej odpovedi nie vždy odpovedia nie, a ukazuje, že P ⊆ RP ⊆ NP, pretože náhodné bity možno nahradiť nedeterministickými krokmi. Analogicky triedu coRP umiestňuje medzi P a coNP. Na záver začína obojstranné Monte Carlo algoritmy, ktoré sa môžu mýliť v oboch prípadoch, no správnu odpoveď dávajú s pravdepodobnosťou aspoň 1/2.

• - Trieda P: problémy riešiteľné deterministickým polynomiálnym algoritmom; P ⊆ NP.
• - NP: nedeterministický výpočet s orákulom nájde najkratšiu vetvu k odpovedi áno; pre odpoveď nie nie je garantovaný polynomiálny čas.
• - coNP: opačná definícia, hľadá sa najkratšia vetva k odpovedi nie.
• - RP: jednostranné Monte Carlo algoritmy, pri správnej odpovedi nie vždy odpovedia nie, pri áno sa môžu mýliť.
• - P ⊆ RP ⊆ NP: náhodné bity sa nahradia nedeterministickými krokmi, a deterministický algoritmus je triviálne Monte Carlo bez náhodných bitov.
• - coRP je zrkadlová trieda k RP (áno je vždy správne) a leží medzi P a coNP.
• - Obojstranné Monte Carlo algoritmy sa môžu mýliť v oboch prípadoch, správnu odpoveď dávajú s pravdepodobnosťou aspoň 1/2.

Zhrnutie pripravené s pomocou AI z prepisu videa.