Concepte în Informatică
Pritesh Patel
Computer Scientist & Data Scientist for over 20 years
Clase de complexitate


| Clasă de complexitate --> | P (Timp polinomial) |
|---|---|
| Semnificație | Rezolvabil rapid și eficient |
| Exemplu | Sortarea unei liste |
| Analogie | „Clasarea documentelor în ordine alfabetică" |
| Punct cheie | Sunt considerate „ușoare" în termeni computaționali |

| Clasă de complexitate --> | NP (Timp polinomial nedeterminist) |
|---|---|
| Semnificație | Soluția poate fi verificată, dar e greu de găsit |
| Exemplu | Verificarea corectitudinii unui puzzle Sudoku |
| Analogie | „Găsirea unui document cu informații lipsă" |
| Punct cheie | Verificarea soluțiilor e „ușoară", dar găsirea lor e dificilă |

| Clasă de complexitate --> | NP-Complet |
|---|---|
| Semnificație | Cele mai dificile din NP. Rezolvă toate problemele NP |
| Exemplu | Problema comis-voiajorului |
| Analogie | „Puzzle complex: ușor de verificat, greu de rezolvat" |
| Punct cheie | Nicio soluție eficientă cunoscută, dar găsirea uneia ar rezolva toate NP |

| Clasă de complexitate --> | NP-Dificil |
|---|---|
| Semnificație | La fel de dificil ca NP-Complet sau mai dificil |
| Exemplu | Planificare optimă cu dependențe complexe, neverificabilă |
| Analogie | „Găsirea orei optime pentru o întâlnire cu multe constrângeri, neverificabilă rapid" |
| Punct cheie | Posibil imposibil de rezolvat în practică |

Concepte în Informatică