Opløselighedsproblem

Løsningsproblem ( beslutningsproblem ) er et spørgsmål formuleret inden for rammerne af et formelt system , der kræver et ja eller nej svar, muligvis afhængigt af værdierne af nogle inputparametre [ 1] .

For eksempel problemet "givet to tal: og ; er deleligt med ? er et løselighedsproblem. Svaret kan gives enten "ja" eller "nej" og afhænger af værdierne af og . En metode til at løse et løselighedsproblem, præsenteret i form af en algoritme, kaldes en beslutningsprocedure for dette problem. Således bør løsningsproceduren for problemet fra eksemplet ovenfor bestemme det sæt af handlinger, der skal udføres for at kontrollere heltalsdeleligheden for givne tal . En af disse algoritmer - division med en søjle  - studeres i folkeskolen. En rest lig med nul betyder, at svaret er "ja", ellers - "nej". Et løselighedsproblem, som der er en løsningsprocedure for, kaldes løseligt.

Ikke alle matematiske problemer kan formuleres som løselighedsproblemer. At beregne produktet af to tal, finde den hurtigste algoritme til at gange tal og optimeringsproblemer , især det klassiske rejsende sælgerproblem , er ikke løselighedsproblemer, da de ikke kan formuleres på en sådan måde, at svaret på problemet ville være " Ja eller nej".

Forskning inden for rekursionsteori fokuserer ofte på afgørelighedsproblemer, da mange problemer kan reduceres til dem uden tab af generalitet.

Se også

• Spørgsmål om tilladelse
• Algoritmisk afgørelighed

Noter

1. ↑ Tom Stewart. Teori om computing for programmører . - Liter, 2015-06-24. - S. 329. - 386 s. — ISBN 9785457831230 .

Litteratur

• Maltsev A. I. , Algoritmer og rekursive funktioner , Nauka, 1986.
• Daniel Kroening & Ofer Strichman, Decision procedures , Springer, ISBN 978-3-540-74104-6
• Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability , MIT Press , ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1