miniatura|249x249px|O problemă de decizie are două ieșiri posibile (DA sau NU) pentru orice intrare În teoria calculabilității și în teoria complexității, o problemă de decizie este o care poate fi formulată sub forma unei pe o mulțime de valori de intrare. Un exemplu de problemă de decizie este dacă un număr natural dat este prim. Un alt exemplu este problema: „date fiind două numere x și y, x îl divide pe y?”

O procedură de decizie pentru o astfel de problemă este o metodă algoritmică care dă răspunsul la întrebarea cu da-nu pentru orice intrare, și o problemă de decizie se numește dacă există o procedură de decizie pentru ea. De exemplu, problema de decizie „date fiind două numere x și y, x îl divide pe y?” este decidabilă, deoarece există o procedură de decizie numită care dă pașii pentru a determina dacă x îl divide pe y și răspunsul corect corespunzător, DA sau NU. Unele din cele mai importante probleme din matematică sunt , cum ar fi problema opririi.

Domeniul teoriei complexității categorisește problemele de decizie decidabile după cât de dificil sunt ele de rezolvat. „Dificil”, în acest sens, se descrie în termeni de necesare de cel mai eficient algoritm pentru o anume problemă. Pe de altă parte, domeniul teoriei calculabilității categorisește problemele de decizie indecidabile după , o mășură a necalculabilității inerente în orice soluție.

Definiție O problemă de decizie este limbajul formal al tuturor intrărilor pentru care ieșirea (răspunsul la întrebarea cu da-nu pentru o intrare dată) este DA.

Aceste intrări pot fi numere naturale, dar pot fi și valori de alt fel, ca binare sau alte șiruri de simboluri dintr-un alfabet.

De exemplu, dacă fiecare intrare poate fi codificată în alfabetul , atunci o problemă a deciziei este o submulțime .

Pentru alt exemplu, folosirea unei codificări cum ar fi , orice șir poate fi codificat ca număr natural, prin intermediul căruia o problemă de decizie se poate defini ca submulțime a mulțimii numerelor naturale. Ca urmare, procedura de decizie a unei probleme de decizie implică calculul a unei submulțimi a mulțimii numerelor naturale.

Exemple Un exemplu clasic de problemă de decizie decidabilă este mulțimea numerelor prime. Se poate decide efectiv dacă un număr natural este prim testând fiecare factor netrivial posibil. Deși se cunosc proceduri mult mai eficiente de , existența oricărei proceduri efective este suficientă pentru a stabili decidabilitatea.

Decidabilitatea

O problemă de decizie este decidabilă sau efectiv rezolvabilă dacă mulțimea de intrări pentru care răspunsul este DA este o . O problemă de decizie este parțial decidabilă, semidecidabilă, rezolvabilă, sau demonstrabilă dacă mulțimea de intrări pentru care răspunsul este DA este o .

Problemele care nu sunt decidabile se numesc indecidabile, ceea ce înseamnă că nu se poate crea un algoritm (eficient sau nu) care le rezolvă. Problema opririi este o problemă de decizie indecidabilă importantă.

Problemele complete Problemele de decizie pot fi ordonate după și puse în legătură cu reducerile fezabile, cum ar fi . O problemă de decizie P este pentru o mulțime de probleme de decizie S dacă P este membru al lui S și orice problemă din S se poate reduce la P. Problemele de decizie complete sunt folosite în teoria complexității pentru a caracteriza clasele de complexitate ale problemelor de decizie. De exemplu, problema satisfiabilității booleene este completă pentru clasa NP de probleme de decizie în raport cu reductibilitatea în timp polinomial.

Probleme de calcul Problemele de decizie sunt în legătură apropiată cu , care pot avea răspunsuri mai complexe decât un simplu DA sau NU. O problemă funcție corespunzătoare ar fi „date fiind două numere x și y, cât este x împărțit la y?”.

O constă dintr-o f; „problema” informală este de a calcula valorile lui f pe intrările pe care este definită.

Orice problemă de calcul poate fi transformată într-o problemă de decizie; problema de decizie este doar graficul funcției asociate. (Graficul unei funcții f este mulțimea de perechi (x,y) astfel încât f(x) = y.) Dacă problema de decizie este rezolvabilă efectiv, atunci și problema de calcul este. Această reducere nu respectă însă complexitatea computațională. De exemplu, se poate ca graficul unei funcții să fie decidabil în timp polinomial (caz în care timpul de rulare se calculează ca funcție de perechea (x,y)), pe când funcția să nu fie calculabilă în timp polinomial (caz în care timpul de rulare se calculează doar ca funcție de x). Funcția f(x) = 2x are această proprietate.

Fiecare problemă de decizie poate fi convertită în problema de calcul a a mulțimii asociate cu problema de decizie. Dacă această funcție este calculabilă, atunci problema de decizie asociată este decidabilă. Această reducere este însă mai liberală decât reducerea standard folosită în teoria complexității (denumită uneori reducere multi-unu în timp polinomial); de exemplu, complexitatea funcțiilor caracteristice ale unei probleme NP-complete și ale ei este exact același chiar dacă problemele de decizie care stau la baza lor nu pot fi considerate echivalente în unele modele tipice de calcul.

Probleme de optimizare Spre deosebire de problemele de decizie, pentru care există un singur răspuns corect pentru fiecare intrare, problemele de optimizare caută cel mai bun răspuns la o anume intrare. Problemele de optimizare apar natural în multe aplicații, cum ar fi problema comis-voiajorului și multe chestiuni de programare liniară.

Problemele de calcul și de optimizare sunt adesea transformate în probleme de decizie considerând întrebarea dacă răspunsul este egal sau mai mic sau egal cu o valoare dată. Aceasta permite studierea complexității problemei de decizie; și în multe cazuri funcția originară de calcul sau problema de optimizare pot fi rezolvate prin rezolvarea problemei de decizie corespunzătoare. De exemplu, în problema comis-voiajorului, problema de optimizare este de a produce un tur cu pondere minimă. Problema de decizie asociată este: pentru orice N, să se decidă dacă graful are un tur cu pondere mai mică decât N. Răspunzând repetat la problema de decizie, se poate găsi ponderea minimă a unui tur.

Întrucât teoria problemelor de decizie este foarte bine dezvoltată, cercetările de teoria complexității s-au concentrat adesea pe problemele de decizie. Problemele de optimizare sunt ele însele de interes în teoria calculabilității, precum și în domenii ca .

Note de completare

Note bibliografice

Bibliografie

Categorie:Logică matematică