RP Randomizované polynomiálním čase je složitost třídy výpočetní složitosti teorie, problémy, pro které pravděpodobnostní Turingův stroj existuje s těmito vlastnostmi:⁕To vždy běží v polynomiálním čase ve vstupním velikost⁕Případě, že správná odpověď je NE, to vždy vrátí ŽÁDNÉ⁕Případě, že správná odpověď je ANO, pak se to vrátí ANO s pravděpodobností alespoň 1/2.Jinými slovy, algoritmus je dovoleno flip skutečně náhodné mince, zatímco to běží. Jediný případ, kdy algoritmus může vrátit Ano, je, pokud je skutečná odpověď Ano; pokud tedy algoritmus ukončí a vytvoří ano, pak správná odpověď je určitě ano; algoritmus však může ukončit ne 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, i když tento název je běžněji používán pro třídu rekurzivních jazyků.Pokud je správná odpověď Ano a algoritmus je spuštěn n krát s výsledkem každého běhu statisticky nezávislého na ostatních, pak se vrátí ano alespoň jednou s pravděpodobností alespoň 1-2−. Takže pokud algoritmus je běh 100 krát, pak je šance, že to dává špatnou odpověď pokaždé, když je nižší, než šance, že kosmické záření poškození paměti počítače spuštěním algoritmu. V tomto smyslu, pokud je k dispozici zdroj náhodných čísel, je většina algoritmů v RP velmi praktická.

Zobrazit více “