Indecidabilitate și intractabilitate

Continuând seria de posturi de cultură generală pentru programatori(am mai zis că nu sună bine în română), o să încerc să alunec puțin dinspre tehnic înspre filosofic.

Este de bun simț să admitem că știința progresează, dovadă că în fiecare război se găsesc noi mijloace de ucide oameni(dacă ne gândim bine, și calculatoarele au fost construite tot cu ocazia războiului). Cu toate că progresează, în secolul 20 s-a ajuns la concluzia că știința nu ne va putea da niciodată toate răspunsurile.

O expresie filosofică a acestui adevăr o aduce Blaga, afirmând că nu putem trece, cu ajutorul cunoașterii, de limita impusă de Marele Anonim. O abordare mai pragmatică și recunoscută de lumea științifică vine de la Kurt Gödel, care prin 1931, arată nu numai că sistemul nostru de axiome este incomplet, ci și că nu avem cum să construim unul complet.

Ce înseamnă acest lucru? Păi axiomele sunt niște adevăruri pe care se bazează toate cunoștințele noastre. Pornind de la aceste axiome ca fundație, începem să construim: cărămidă cu cărămidă, găsim noi teoreme, dar la un moment dat vrem să punem undeva o cărămidă și nu putem, pentru că acolo lipsește fundația, și fără fundație nu putem construi. Nici o problemă, s-ar zice, mai punem fundație(aka acceptăm noi axiome), dar la un moment dat iar ajungem într-un punct unde nu putem construi. Gödel a demonstrat că în afară de sistemele triviale, oricâtă fundație am avea, tot nu vom putea construi orice. La un moment dat, se va enunța o teoremă, despre care nu vom putea ști dacă e adevărată sau nu, oricât ne-am strădui.

Revenind la calculatoarele noastre, nu știu câți și-au pus întrebarea ”Ce se poate calcula?” sau ”La ce întrebări ne poate răspunde calculatorul?”. Din mulțimea de întrebări posibile, nu o să le alegem pe cele de genul ”what is the answer to life the universe and everything”… asta e ușoară, răspunsul e 42(întrebați pe google dacă nu mă credeți). Ne vom lega de acum încolo de întrebările la care se poate răspunde cu DA sau nu, numite și probleme de decizie. Exemple de astfel de întrebări sunt ”Este 25 mai mare ca 20?”sau ”Se poate găsi un drum pe harta României, care să treacă prin fiecare oraș o singură dată?” sau încă ”Dacă rulăm algoritmul ăsta, o să se termine vreodată?”.

Evident, pentru întrebări de genul primeia, răspunsul se găsește imediat. Sărim deocamdată peste a doua, și ne uităm la cea de-a 3-a. Ca să o exprimăm mai precis, vrem să scriem un program care să analizeze un alt program, și să ne spună dacă se termină, sau buclează la infinit. Tot prin anii ’30, Alan Turing a demonstrat că un astfel de program nu se poate scrie. Spunem deci, că această problemă este indecidabilă. Desigur, putem să rulăm efectiv programul care se cere analizat, iar dacă se termină am câștigat: putem răspunde cu certitudine DA. Dacă în schimb după 10 minute sau după 10 luni, programul tot rulează, nu avem de unde ști dacă face calcule utile și la un moment dat va ajunge la rezultat, sau s-a împotmolit într-o buclă infinită.

Dacă ne întoarcem la a doua întrebare, care pentru cunoscători se numește problema ciclului Hamiltonian, observăm că putem găsi o soluție: încercăm fiecare drum posibil în parte, iar la un moment dat, fie am epuizat toate drumurile, fie am găsit un drum cu proprietatea cerută. Deși această abordare va da până la urmă un răspuns la întrebare, avem de încercat o groază de variante. Mai rău, pentru cei ce au citit postul anterior din această categorie, putem spune că algoritmul are o complexitate exponențială, adică să zicem că avem un calculator suficient de rapid care să rezolve problema pentru un anumit număr de orașe în timp rezonabil, dacă mai introducem chiar și un număr foarte mic de orașe în ecuație, nu se va mai găsi răspuns într-un timp acceptabil.

Partea cu adevărat proastă la problema de mai sus este că nici până în zilele noastre nu s-a găsit vreo abordare mai bună, care să rezolve problema în timp polinomial. Singurul lucru care mai salvează cât de cât situația este faptul că dacă cineva găsește din întâmplare un drum, putem verifica destul de repede(în timp polinomial) dacă soluția este corectă sau nu. De fapt, foarte multe probleme cu care ne întâlnim în practică au proprietatea de a li se putea verifica soluția în timp polinomial. Vom nota această clasă de probleme cu NP. Desigur, în această clasă de probleme intră și cele simple, care se pot rezolva în timp polinomial, a căror clasă o notăm cu P, deci avem P \subseteq NP.

Una dintre problemele mileniului, pentru care se oferă un premiu de 1 milion de dolari, este verificarea dacă e incluziune strictă, sau avem egalitate, între cele două clase de probleme. Partea care stă în calea egalității, e un anumit grup de probleme, numite NP-complete, sau intractabile, de genul celei amintite mai sus, pentru care nu s-a găsit încă un algoritm polinomial, dar nici nu s-a putut demonstra că nu ar exista. Este surprinzător faptul că toate aceste probleme, din domenii atât de diferite, se pot reduce în timp polinomial una la alta. De exemplu, dacă reușim să găsim o soluție în timp polinomial la problema împărțirii unei mulțimi de numere, în două mulțimi cu sume egale(pentru olimpicii la info care cred că au soluția, trebuie să repet că vreau timp polinomial, nu pseudopolinomial), vom putea rezolva în timp polinomial și problema ciclului Hamiltonian amintită mai sus.

Acest fapt remarcabil, posibilitatea reducerii, ne ușurează de multe ori viața în practică. Când întâlnim o problemă la care nu putem găsi soluție în timp polinomial, putem încerca să o reducem la o problemă NP-completă cunoscută, iar dacă reușim reducerea, înseamnă că am întâlnit o problemă cu care informaticienii și matematicienii se confruntă fără succes de decenii, și probabil ar fi cazul să ne petrecem timpul cu ceva mai util, de exemplu să încercăm să dăm o soluție aproximativă, sau să facem un backtracking cât mai optimizat.

Concluzia pe care cititorul ar trebui să o tragă din cele citite mai sus, este că nu orice problemă se poate rezolva cu ajutorul calculatorului, și chiar și pentru cele care se pot rezolva, nu putem găsi tot timpul o rezolvare care să dea soluția în timp acceptabil. Cu toate acestea, putem construi soluții imperfecte, care să ajute utilizatorul, și care să încerce să se apropie cât mai mult de perfecțiune.

Anunțuri
Published in: on Februarie 19, 2010 at 16:53  Comments (3)  

The URI to TrackBack this entry is: https://just1coder.wordpress.com/2010/02/19/indecidabilitate-%c8%99i-intractabilitate/trackback/

RSS feed for comments on this post.

3 comentariiLasă un comentariu

  1. Salut. Scuze de deranj, dar fiind hunedorean ca si tine , indraznesc intr-o oarecare masura sa iti cer ceva. Ai putea sa imi trimiti pe mail, cursuri, exercitii, orice legat de spatii afine si de actiunea unui grup? Iti raman recunascator. Mersi mult!
    adresa email: egozenovius@yahoo.com

  2. Ceau. Am primit mail-ul de la tine. M-a ajutat cea ce mi-ai trimis. Iti multumesc mult si bafta la facultate!


Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s

%d blogeri au apreciat asta: