Mi az a döntési probléma?

K: Mi az a döntési probléma?

V: A döntési probléma egy olyan kérdés valamilyen formális rendszerben, amelyre a válasz igen vagy nem, a bemeneti paraméterek értékeitől függ.

K: Milyen tudományterületeken fordulnak elő döntési problémák?

V: A döntési problémák jellemzően a matematikai eldönthetőségi kérdésekben jelennek meg.

K: Mit jelent a eldönthetőség?

V: A eldönthetőség arra a kérdésre utal, hogy létezik-e hatékony módszer valamilyen objektum létezésének vagy egy halmazhoz való tartozásának meghatározására.

K: Minden matematikai probléma eldönthető?

V: Nem, a matematika legfontosabb problémái közül néhány nem eldönthető.

K: Mi az a nem eldönthető probléma?

V: A nem eldönthető probléma olyan probléma, amelyre nem létezik olyan algoritmus, amely véges időn belül mindig igen vagy nem választ adna.

K: Egy döntési problémára mindig igen vagy nem a válasz?

V: Igen, egy döntési problémára a válasz mindig igen vagy nem.

K: Mitől függ egy döntési problémára adott válasz?

V: A döntési problémára adott válasz a bemeneti paraméterek értékeitől függ.