Třída PTIME

Do této třídy složitosti spadají všechny problémy řešené s polynomiálními algoritmy.

PTIME = Τ(nk),

kde k je konstanta (0,∞). Třídu těchto problému považujeme za zvládnutelnou. Tato třída je robustní. Robustnost třídy znamená nezávislost na zvoleném modelu počítačů. Je tedy jedno zda algoritmus budeme implementovat na Turingově či RAM stroji, složitost problému zůstane v PTIME třídě.

Do této třídy spadá mnoho praktických problému:

  • Třídění
  • Vyhledávání
  • Aritmetické operace
  • Ekvivalence determistických konečných automatů
  • Nejkratší cesta v grafu
  • Minimální kostra grafu
  • Přijatelnost slova bezkontextovou gramatikou
  • Výběr aktivit
    Vstup: Množina aktivit s časovými intervaly, kdy je lze vykonávat.
    Výstup: Největší možný počet kompatibilních aktivit (aktivit, které se nekryjí)
  • Optimalizace násobení řetězce matic
    Vstup: Posloupnost matic
    Výstup: Plně uzávorkovaný součin
  • LCS - problém nejdelší společné posloupnosti
    Vstup: Dvě posloupnosti v,w v nějaké abecedě Σ
    Výstup: Nejdelší společná podposloupnost posloupností v,w.