RP (složitost) - RP (complexity)
V teorii výpočetní složitosti je randomizovaný polynomiální čas ( RP ) třídou složitosti problémů, pro které existuje pravděpodobnostní Turingův stroj s těmito vlastnostmi:
| RP algoritmus (1 běh) | ||
|---|---|---|
|
Odpověď byla vyprodukována
Správná
odpověď |
Ano | Ne |
| Ano | ≥ 1/2 | ≤ 1/2 |
| Ne | 0 | 1 |
| Algoritmus RP ( n běhů) | ||
|
Odpověď byla vyprodukována
Správná
odpověď |
Ano | Ne |
| Ano | ≥ 1 - 2 - n | ≤ 2 - n |
| Ne | 0 | 1 |
| algoritmus co-RP (1 běh) | ||
|
Odpověď byla vyprodukována
Správná
odpověď |
Ano | Ne |
| Ano | 1 | 0 |
| Ne | ≤ 1/2 | ≥ 1/2 |
- Vždy běží v polynomiálním čase ve velikosti vstupu
- Pokud je správná odpověď NE, vždy vrátí NE
- Pokud je správná odpověď ANO, vrátí ANO s pravděpodobností alespoň 1/2 (jinak vrátí NE).
Jinými slovy, algoritmu je dovoleno převrátit skutečně náhodnou minci, když je spuštěna. Jediný případ, kdy může algoritmus vrátit ANO, je, pokud je skutečná odpověď ANO; proto pokud algoritmus končí a produkuje ANO, pak je správná odpověď rozhodně ANO; algoritmus však může být ukončen NO bez ohledu na skutečnou odpověď. To znamená, že pokud algoritmus vrátí NE, může to být špatně.
Někteří autoři nazývají tuto třídu R , ačkoli se tento název běžněji používá pro třídu rekurzivních jazyků .
Pokud je správná odpověď ANO a algoritmus je spuštěn nkrát s výsledkem každého spuštění statisticky nezávislým na ostatních, vrátí ANO alespoň jednou s pravděpodobností alespoň 1 - 2 - n . Pokud je tedy algoritmus spuštěn stokrát, pak je šance, že pokaždé poskytne nesprávnou odpověď, menší než šance, že kosmické paprsky poškodily paměť počítače, na kterém je algoritmus spuštěn. V tomto smyslu, pokud je k dispozici zdroj náhodných čísel, je většina algoritmů v RP velmi praktická.
Frakce 1/2 v definici je libovolná. Sada RP bude obsahovat přesně stejné problémy, i když je 1/2 nahrazena jakoukoli konstantní nenulovou pravděpodobností menší než 1; konstantní zde znamená nezávislý na vstupu do algoritmu.
Formální definice
Jazyk L je v RP právě tehdy, pokud existuje pravděpodobnostní Turingův stroj M , takový
- M běží na polynomiálním čase na všech vstupech
- Pro všechna x v L , M výstupy 1 s pravděpodobností větší nebo rovnou 1/2
- Pro všechna x, která nejsou v L , M výstupy 0
Alternativně lze RP definovat pouze pomocí deterministických Turingových strojů. Jazyk L je v RP právě tehdy, existuje-li polynom p a deterministický Turingův stroj M , takový
- M běží na polynomiálním čase na všech vstupech
- Pro všechna x v L je podíl řetězců y délky p (| x |), které splňují, větší nebo roven 1/2
- Pro všechna x ne v L a všechny řetězce y délky p (| x |),
V této definici řetězec y odpovídá výstupu náhodných převrácení mince, které by pravděpodobnostní Turingův stroj udělal. Pro některé aplikace je tato definice výhodnější, protože nezmiňuje pravděpodobnostní Turingovy stroje.
Související třídy složitosti
Definice RP říká, že odpověď ANO je vždy správná a odpověď NE může být špatná, protože instance ANO může vrátit odpověď NE. Co-RP třídy složitosti je kompliment, kde odpověď ANO může být špatná, zatímco odpověď NE je vždy správná.
Třída BPP popisuje algoritmy, které mohou poskytovat nesprávné odpovědi v instancích ANO i NE, a tedy obsahuje RP i co-RP . Průsečík množin RP a co-RP se nazývá ZPP . Stejně jako RP lze nazvat R , někteří autoři používají název co-R spíše než co-RP .
Připojení k P a NP
P je podmnožina RP , což je podmnožina NP . Podobně je P podmnožinou co-RP, která je podmnožinou co-NP . Není známo, zda jsou tyto inkluze přísné. Pokud je však běžně věřená domněnka P = BPP pravdivá, pak se RP , co-RP a P zhroutí (všechny jsou stejné). Za předpokladu, že navíc P ≠ NP , to pak znamená, že RP je přísně obsažen v NP . Není známo, zda RP = co-RP , nebo zda RP je podmnožinou průsečíku NP a co-NP , i když by to znamenalo P = BPP .
Přirozeným příkladem problému v co-RP, o kterém v současné době není známo, že je v P, je Polynomial Identity Testing , problém rozhodování, zda daný vícerozměrný aritmetický výraz přes celá čísla je nula-polynom. Například x · x - y · y - ( x + y ) · ( x - y ) je nulový polynom, zatímco x · x + y · y není.
Alternativní charakterizací RP, která je někdy snazší, je sada problémů rozpoznatelných nedeterministickými Turingovými stroji, kde stroj přijímá právě tehdy, pokud akceptuje alespoň nějaký konstantní zlomek výpočetních cest, nezávisle na velikosti vstupu. NP na druhé straně potřebuje pouze jednu akceptační cestu, která by mohla tvořit exponenciálně malý zlomek cest. Tato charakterizace činí skutečnost, že RP je podmnožinou NP, zřejmá.