Algoritmická rozhodnutelnost (řešitelnost) problému
Problém je rozhodnutelný (řešitelný) pokud pro libovolný vstup z množiny vsupů, skončí algoritmus svůj výpočet a vydá správný výstup.
Pokud tedy najdu takový vstup problému, na kterém si všechny dosavadní algoritmy řešící tento problém vylámou zuby, můžu tento problém nazvat neřešitelný. Důkaz neřešitelnosti lze provést také skrze jiné - už dokázané - problémy. Speciální případ jsou doplňkové problémy, které vracejí přesně opačné výsledky než původní problém.
Definice problému 
:
Problém je určen trojicí (IN,OUT, p), kde IN je množina (přípustných) vstupů, OUT je množina výstupů a
p : IN → OUT je funkce přiřazující každému vstupu odpovídající výstup.
Ano/Ne problémy
Jsou to problémy, jejichž výstupní množina obsahuje dva prvky OUT={ano, ne}.
Na ano/ne problémy se dají převést ostatní problémy nepotřebujeme-li znát přesný výsledek. Například:
- nepotřebuji najít v poli nejmenší číslo, stačí mi vědět zda pole obsahuje číslo menší než nula.
- nepotřebuji znát nejkratší cestu grafem, ale stačí mi najít cestu která je kratší než 8.
Optimalizační problémy
Optimalizační problémy hledají nejlepší řešení. V množině různých řešení hledáme to nejlepší. Příkladem je například hledání nejkratší cesty, nejmenší kostry, apod.
Název: Nejkratší cesta v grafu
Vstup: Orientovaný graf G = (V,E) a dvojice vrcholů u, v ∈ V .
Výstup: Nejkratší cesta z u do v.
Název: Minimální kostra
Vstup: Neorientovaný souvislý graf G = (VG,EG) s ohodnocenými hranami
Výstup: Souvislý graf H = (VH,EH), kde VH = VG a EH ⊆ EG, který má součet hodnot všech hran minimální.
Nerozhodnutelné problémy
Název: Eq-CFG (Ekvivalence bezkontextových gramatik)
Vstup: Dvě bezkontextové gramatiky G1,G2.
Otázka: Platí L(G1) = L(G2)? Generují obě gramatiky stejný jazyk?
Název: HP (Problém zastavení [Halting Problem] )
Vstup: Turingův stroj M a jeho vstup w.
Otázka: Zastaví se M na w (tzn. je výpočet stroje M pro vstupní slovo w konečný)?