decision problem

Angol

Főnév

decision problem (tsz. decision problems)

(informatika)

A decision problem (döntési probléma, Entscheidungsproblem) az elméleti számítástechnika egyik alapfogalma, amely olyan kérdés, amelyre a válasz mindig „igen” vagy „nem”. Minden számítási probléma átszabható döntési problémává, így ezek központi szerepet játszanak a komplexitáselméletben, különösen a P, NP, és NP-complete osztályok definícióiban.

🧠 1. Definíció

Egy döntési probléma olyan probléma, amely bemenetként egy objektumot (pl. egy sztringet vagy gráfot) kap, és eldönti, hogy az eleme-e egy adott halmaznak.

Formálisan:

Legyen ${\textstyle L\subseteq \Sigma ^{*}}$ egy nyelv (szimbólumok halmazából álló sztringek halmaza).
A döntési probléma: „Adott ${\textstyle x}$ , eldönthető-e, hogy ${\textstyle x\in L}$ ?”

✅ 2. Jellemzők

Tulajdonság	Jelentés
Bemenet	Egy bináris vagy karakterlánc
Kimenet	„IGEN” (1) vagy „NEM” (0)
Példa kérdés	„Van-e a gráfban Hamilton-kör?”
Döntési mód	Egy algoritmus vagy gép eldönti

📦 3. Példák döntési problémákra

Probléma	Kérdés
Prímszám-ellenőrzés	„A szám prímszám?”
Rendezett-e?	„A lista elemei növekvő sorrendben vannak?”
Satisfiability (SAT)	„Létezik-e változóértékadás, amely kielégíti a formulát?”
Hamiltonian cycle	„Van-e Hamilton-kör a gráfban?”
Knapsack decision	„Létezik-e tárgykiválasztás, ami nem lépi túl a súlykorlátot és elér egy adott értéket?”

🔁 4. Miért fontosak a döntési problémák?

Formális elemzés alapja: a legtöbb komplexitási osztály (pl. P, NP, PSPACE) döntési problémákat tartalmaz.
NP-complete problémák: mindig döntési változatként definiáljuk őket.
Redukciók és bizonyítások döntési problémák között történnek.

🧮 5. Optimalizálási vs. döntési probléma

Típus	Példa
Optimalizálás	„Mi a legnagyobb érték, amit elérhetünk?”
Döntési	„Van-e megoldás legalább ennyi értékkel?”

Megjegyzés: Az optimalizálási probléma gyakran döntési problémává alakítható, és így vizsgálható komplexitáselméleti szempontból.

🧰 6. Példa Pythonban – döntési logika (pl. prímszám)

def is_prime(n):
    if n < 2:
        return False
    for d in range(2, int(n**0.5)+1):
        if n % d == 0:
            return False
    return True

print(is_prime(7))  # → True
print(is_prime(9))  # → False

📊 7. Osztályok döntési problémák szerint

Osztály	Döntési probléma tulajdonsága
P	Megoldható determinisztikusan polinomiális idő alatt
NP	Ellenőrizhető polinomiális idő alatt
NP-complete	Legnehezebb NP-problémák
co-NP	„NEM” válasz ellenőrizhető gyorsan
PSPACE	Megoldható polinomiális memóriahasználattal

📚 8. Formális példa – 3-SAT döntési probléma

Bemenet: Egy logikai formula, ami csak három literálból álló zárójeles klauzulákból áll. Kérdés: Van-e olyan változóértékadás, amely kielégíti az összes klauzulát?

Ez a klasszikus NP-complete döntési probléma.

🧾 9. Összefoglalás

Fogalom	Leírás
Döntési probléma	Olyan probléma, amelyre a válasz „igen” vagy „nem”
Fontosság	Alapja a komplexitáselméletnek
Optimalizálás vs döntés	Az optimalizálás gyakran átalakítható döntésre
Példák	SAT, Hamilton-kör, Knapsack döntési változata
Alkalmazás	P vs NP kérdés, bonyolultsági osztályok, bizonyítások

További információk

decision problem - Szótár.net (en-hu)
decision problem - Sztaki (en-hu)
decision problem - Merriam–Webster
decision problem - Cambridge
decision problem - WordNet
decision problem - Яндекс (en-ru)
decision problem - Google (en-hu)
decision problem - Wikidata
decision problem - Wikipédia (angol)