navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
statnice:spolecne:reseni_prikladu_ze_zkousek_tal [2012/05/21 18:33] destil |
statnice:spolecne:reseni_prikladu_ze_zkousek_tal [2025/01/03 18:29] (aktuální) |
||
|---|---|---|---|
| Řádek 127: | Řádek 127: | ||
| Kterýkoli NP problém, třeba obchodní cestující. | Kterýkoli NP problém, třeba obchodní cestující. | ||
| - | ==== Vztah mezi P, NP, PSPACE, NPSPACE ==== | + | ==== Vztah mezi P, NP, PSPACE, NPSPACE, EXP ==== |
| - | P ⊆ NP ⊆ (PSPACE=NPSPACE) | + | P ⊆ NP ⊆ (PSPACE=NPSPACE) ⊆ EXP |
| - | ==== Vztah mezi rekurzivne spocetnymi jazyky a NPSPACE ==== | ||
| - | ==== Třída EXP je třída všech jazyků přijímaných TS v exponenciálním čase (nebo něco v tom smyslu), určit vztah mezi EXP, NPSPACE, NP, co-NP ==== | ||
| ==== Definujte tridu jazyku RP a ZPP ==== | ==== Definujte tridu jazyku RP a ZPP ==== | ||
| + | Jazyk patří do RP, pokud ho rozhoduje randomizovaný TS (TS s další náhodnou páskou) a ANO instance odhalí s pravděpodobností > 50%. | ||
| + | |||
| + | Jazyk patří do ZPP, když rozhodne jazyk randomizovaným TS pro ANO i NE instance. | ||
| + | |||
| ==== Reknete priklad jazyka patriciho do RP ==== | ==== Reknete priklad jazyka patriciho do RP ==== | ||
| - | ==== Třída co-RE je doplněk jazyka RE. Co platí pro třídy R, RE, co-RE a třídu úplně všech jazyků VS. Napiš všechny inkluze, které platí. Pokud jsou některé tyto inkluze ostré, uveď příklad jazyka ==== | + | Rabin-Millerův test přijímá složená čísla s pravděpodobností 75% a pro žádné prvočíslo neprohlásí, že je složené. |
| + | |||
| + | |||
| ==== Co jsou to rekurzivní a rekurzivně spočetné jazyky. ==== | ==== Co jsou to rekurzivní a rekurzivně spočetné jazyky. ==== | ||
| * Rekurzivní jazyk, pokud existuje TS, který se na každém vstupu zastaví a jazyk rozhodne ANO/NE. | * Rekurzivní jazyk, pokud existuje TS, který se na každém vstupu zastaví a jazyk rozhodne ANO/NE. | ||
