Lucka Žoltá

Třída NPTIME

Třída NPTIME zahrnuje všechny rozhodovací (ano/ne) problémy, které jsou rozhodovány nedeterministickými polynomiálními algoritmy - tedy nedeterministickými algoritmy s polynomiální časovou složitosti O(n^c).

Nedeterministický algoritmus rozhoduje ano/ne problémy, ale ne vždy správně. Při odpovědi 'ano' je výsledek vždy správný (našel se alespoň jeden výpočet pro který je odpověď ano) zatímco odpověď 'ne' nemusí být vždy pravdivá a to z důvodu, že by na výstupu muselo být vždy ne (algoritmus by musel otestovat všechny možnosti).

Pointou nedeterministických algoritmů je to že náhodně nastřelují nějaké řešení a ověřují jejich správnost.

Například nedeterministický algoritmus pro problém IS (viz. obrázek a definice níže) vybere náhodně k vrcholů z grafu a ověří zdali nejsou některé spojeny hranou. Když mezi nimi hranu nenajde, vráti odpověď "ANO, v grafu existuje nezávislá množina o velikosti k ". Když hranu mezi zvolenou množinou najde, vrátí odpověď "NE". Přičemž odpověď ne může být chybná. Třeba pro graf ABCDE na obrázku níže a k=3, vybere algoritmus vrcholy {A, B, C}, které závislé jsou a vrátí chybnou odpověď "NE". Když to ale algoritmus provede vícekrát, pro různé vrcholy, pravděpodobnost správnosti odpovědi se zvyšuje. A o tom to je. Nepotřebujeme znát 100% správnou odpověď, ale chceme se dočkat alespoň nějaké odpovědi.

Problémy třídy NPTIME

Název: IS (problém nezávislé množiny [Independent Set] (také nazývaný problém anti-kliky [anti-clique]))

Vstup: Neorientovaný graf G (o n vrcholech); číslo k (k ≤ n).
Otázka: Existuje v G nezávislá množina velikosti k (tj. množina k vrcholů, z nichž žádné dva nejsou spojeny hranou)?

Název: Složenost čísla

Vstup: Přirozené číslo ℓ.
Otázka: Je číslo ℓ složené (dělitelné beze zbytku)?

Název: Isomorfismus grafů

Vstup: Dva neorientované grafy G a H.
Otázka: Jsou grafy G a H izomorfní?

Název: CG (Barvení grafu)

Vstup: Neorientovaný graf G a číslo k.
Otázka: Je možné graf G obarvit k barvami (tj. existuje přiřazení barev vrcholům tak, aby žádné dva sousední vrcholy nebyly obarveny stejnou barvou)?

Název: SAT (problém splnitelnosti booleovských formulí)

Vstup: Booleovská formule v konjunktivní normální formě.
Otázka: Je daná formule splnitelná (tj. existuje pravdivostní ohodnocení proměnných, při kterém je formule pravdivá)?

Název: HK (problém hamiltonovské kružnice) / HC (problém hamiltonovskho cyklu)

Vstup: Neorientovaný graf G. / Orientovaný grav G.
Otázka: Existuje v G hamiltonovská kružnice (uzavřená cesta, procházející každým vrcholem právě jednou)?

Název: Subset-Sum

Vstup: Množina přirozených čísel M = {x1, x2, . . . , xn} a přirozené číslo s.
Otázka: Existuje podmnožina množiny M, pro niž součet jejích prvků je roven s?