Třída P, třída NP, důvody jejich zavedení, jejich vzájemný vztah

Definice třídy časové a prostorové složitosti

• Pro funkci $f:\mathbb{N}\to \mathbb{N}$ rozumíme třídou časové složitosti $T(f)$, množinu těch probému, které jsou řešeny TS s časovou složitostí v $O(f)$.
• Třídou prostorové složitosti $S(f)$, rozumíme třídu těch problémů, které jsou řešeny TS s prostorovou složitostí v $O(f)$

Time$(f(n))$

• Množina všech problémů, které jsou TS rešitelné s časovou složitostí $O(f(n))$.

PTIME

• Třída obsahující všechny problémy řešitelné algoritmy (TS) s polynomiální časovou složitostí $PTIME={\bigcup }_{k\in \mathbb{N}}Time(n^k)$
• Robustnost třídy PTIME znamená nezávislost na zvoleném referenčním modelu počítačů. Když bychom totiž jako referenční model vzali např. stroje RAM, třída PTIME by se nezměnila.
• Patří sem: dosažitelnost v grafu, nejkratší cesta v grafu, minimální kostra v grafu, třídění, …

Ntime$(f(n))$

• Množina všech $ANO/NE$ problémů, které jsou rozhodované NTS s časovou složitostí $O(f(n))$.

NPTIME

• Třída všech $ANO/NE$ problémů, které jsou rozhodovány nedeterministickými algoritmy s polynomiální časovou složitostí.
• $NPTIME={\bigcup }_{k\in \mathbb{N}}Ntime(n^k)$
• Robustnost třídy NPTIME znamená nezávislost na zvoleném referenčním modelu počítačů. Když bychom totiž jako referenční model vzali např. stroje RAM, třída NPTIME by se nezměnila

Důvod zavedení tříd PTIME a NPTIME

• Třídy časové složitosti PTIME a NPTIME byly vytvořené pro popis a kategorizaci problémů, které jsou řešitelné deterministickými a nedeterministickými algoritmy s polynomiální časovou složitostí.

PSPACE

• Třída obsahující všechny problémy řešitelné algoritmy s polynomiální prostorovou složitostí.

NPSPACE

• Třída obsahující všechny problémy řešitelné nedeterministickými algoritmy s polynomiální prostorovou složitostí.

Vzájemný vztah

$PTIME\subseteq NPTIME\subseteq PSPACE=NPSPACE$

1. $PTIME\subseteq NPTIME$
   • Přes velké úsilí vědecké komunity, zatím nebylo dokázáno, že $PTIME=NPTIME$, ani že $PTIME\ne NPTIME$. To znamená, že stále existuje možnost, že některé problémy, které jsou řešitelné nedeterministickými algoritmy v polynomiálním čase, mohou být řešitelné i deterministickými algoritmy v polynomiálním čase, nebo naopak.
   • Nicméně existuje mnoho problémů, u kterých se věří, že jsou řešitelné nedeterministickými algoritmy v polynomiálním čase, ale nebylo nalezeno žádné deterministické řešení v polynomiálním čase.
   • Tyto problémy jsou považovány za “typické” pro třídu $NPTIME$. Mezi takové problémy patří například problém nalezení Hamiltonovské kružnice v grafu.
     • Název: HK (problém Hamiltonovské kružnice)
     • Vstup: Neorientovaný graf $G$ - Otázka: Existuje v $G$ hamiltonovská kružnice (tj. uzavřená cesta, procházející každým vrcholem právě jednou?
   • Abychom dokázali, že $PTIME\subset NPTIME$, museli bychom najít problém, který patří do $NPTIME$, ale zároveň nepatří do $PTIME$
   • Abychom dokázali, že $PTIME=NPTIME$, tak bychom museli dokázat např. $SAT\in PTIME$
2. $NPTIME\subseteq PSPACE$
   • Pro libovolnou funkci $f$ je $T(f(n))\subseteq S(f(n))$
     • např. Turingův stroj očividně navštíví při výpočtu nejvýše tolik políček, kolik udělá kroků
3. $PSPACE=NPSPACE$
   • Platí podle Savitchovi věty

Navigace

Předchozí: Složitost algoritmu (časová a paměťová) Následující: NP-úplné problémy Celý okruh: 1. Teoretické základy informatiky