Definíció: Probléma egy I (inputok halmaza) halmazból egy O (outputok halmaza) halmazába képezõ függvény.
Definíció: Döntési probléma egy olyan probléma, ahol O az {igen, nem} halmaz.
Általában I a lehetséges inputok egy nagyon pontosan leírt módon (számítógép által is érthetõ) való leírásait (kódolásait) tartalmazza. Egy konkrét kódolás lerögzítésénél I egy véges jelhalmazból (ábc) képzett véges jelsorozatok halmaza lesz.
Példa: Legyen Z={0,1}, legyen G a Z* azon része, amely 0-1 sorozatok megkaphatók egy egyszerû greáf szomszédsági mátrixának sorfolytonos elolvasásával. Tehát az egyszerû gráfok azonosíthatók a Z* egy jól felismerhetõ res'zhalmazával.
Definíció: Legyen Z egy véges ábc. Z-bõl alkotott véges sorozatok halmaza Z*. Z* részhalmazai nyelvek.
Nyelvek azonosíthatók a döntési problémákkal.
Megjegyzés: Az összes egyszerû gráfokra vonatkozó döntési probléma azonosítható egy nyelvvel, amelyben Z={0,1} és L azon 0-1 sorozatok halmaza, amleyek a döntési probléma által elfogadandó egyszerû gráfok kódjai.
Példa: Színezési probléma annak megoldását kéri, hogy egy adott H gráf és k természetes szám esetén döntsük el, hogy H k színnel kiszínezhetõ-e. A megfelelõ SZÍNEZES nyelv: GxN (N a természetes számok halmaza) azon elemeit tartalmazza, amely (H,k) párokra igaz, hogy a H gráf k színezhetõ.
Példa: Hamilton-kör probléma annak megoldását kérti, hogy egy adott H gráf esetén döntsük el, hogy a H gráf tartalmaz-e Hamilton-kört. A megfelelõ HAMILTON nyelv: G azon részhalmaza, amely azon 0-1 részsorozatokat tartalmazza, amelyek által kódolt gráf tartalmaz Hamilton-kört.
Példa: Lefogási probléma annak megoldását kéri, hogy adott H gráf és k természetes szám esetén döntsük el, hogy H lefogható-e k csúccsal. A megfelelõ LEFOGÁS nyelv: GxN azon (H,k) elemit tartalmazza, amelyekre a H gráf lefogható k csúccsal.
Példa: Független halmaz probléma azt kéri, hogy adott H gráf és k természetes szám esetén döntsük el, hogy H-ban létezik-e k független csúcs. A megfelelõ FÜGGETLEN nyelv: GxN azon (H,k) elemit tartalmazza, amelyekre a H gráfban van k független (páronként össze nem kötött csúcs).
Példa: A klikk probléma azt kéri, hogy adott H gráf és k természetes szám esetén döntsük el, hogy H-ban létezik-e k elemû klikk. A megfelelõ KLIKK nyelv: GxN azon (H,k) elemeit tartalmazza, amelyekre a H gráfban van k elemû klikk (páronként összekötött csúcs).
Példa: Párosítási probléma azt kéri, hogy adott H gráf és k természetes szám esetén döntsük el, hogy H-ban létezik-e k független él. A megfelelõ PÁROSÍTÁS nyelv: GxN azon (H,k) elemeit tartalmazza, amelyekre a H gráfban van k független él.
Példa: Teljes párosítási probléma azt kéri, hogy adott H gráf esetén döntsük el, hogy H-ban létezik-e teljes párosítás. A megfelelõ TELJES PÁROSÍTÁS nyelv: G azon H elemeit tartalmazza, amelyekre a H gráfban van teljes párosítás.