Megoldhatósági probléma

A megoldhatósági probléma ( dönthetőségi probléma ) valamilyen formális rendszer keretében megfogalmazott kérdés, amelyre igen vagy nem választ kell adni, esetleg egyes bemeneti paraméterek értékétől függően [1] .

Például a feladat „adott két szám: és ; osztható -vel ? megoldhatósági probléma. A válasz "igen" vagy "nem" adható, és az és értékétől függ . A megoldhatósági probléma megoldására szolgáló módszert, amelyet algoritmus formájában mutatunk be, döntési eljárásnak nevezzük erre a problémára. Így a fenti példából a probléma megoldási eljárásának meg kell határoznia azt a műveletsort, amelyet az egész számok oszthatóságának ellenőrzéséhez kell végrehajtani adott számok esetén. Ezen algoritmusok egyikét - az oszlopos osztást  - az általános iskolában tanulják. A nullával egyenlő maradék azt jelenti, hogy a válasz "igen", egyébként - "nem". Azt a feloldhatósági problémát, amelyre létezik megoldási eljárás, megoldhatónak nevezzük.

Nem minden matematikai probléma fogalmazható meg megoldhatósági problémaként. Két szám szorzatának kiszámítása , a számok leggyorsabb szorzására szolgáló algoritmus megtalálása, valamint az optimalizálási feladatok , különösen a klasszikus utazó eladó probléma , nem megoldhatósági feladatok, mivel nem fogalmazhatók meg úgy, hogy a probléma válasza „ igen vagy nem".

A rekurzióelmélet területén végzett kutatások gyakran a eldönthetőségi problémákra fókuszálnak, mivel sok probléma ezekre redukálható az általánosság elvesztése nélkül.

Lásd még

• Engedély kérdése
• Algoritmikus eldönthetőség

Jegyzetek

1. ↑ Tom Stewart. A számítástechnika elmélete programozóknak . — Liter, 2015-06-24. - S. 329. - 386 p. — ISBN 9785457831230 .

Irodalom

• Maltsev A. I. , Algoritmusok és rekurzív függvények , Nauka, 1986.
• Daniel Kroening és Ofer Strichman, Döntési eljárások , Springer, ISBN 978-3-540-74104-6
• Hartley Rogers, Jr., A rekurzív függvények elmélete és a hatékony kiszámíthatóság , MIT Press , ISBN 0-262-68052-1 (papírkötés), ISBN 0-07-053522-1