Hesablama mürəkkəbliyi nəzəriyyəsi (ing.Computational Complexity Theory) — kompüter elmlərinin bir sahəsi olub, müxtəlif problemlərin həllində istifadə olunan resursların miqdarını (məsələn, vaxt və yaddaş) ölçür və təsnif edir.[1] Bu nəzəriyyə, müxtəlif problemlərin hansı resurslar daxilində həll oluna biləcəyini və hansı problemlərin həlli üçün çox resurs tələb olunduğunu müəyyən etməyə çalışır.[2] Hesablama mürəkkəbliyi nəzəriyyəsi həm də riyazi çətinliklərin və resurs məhdudiyyətlərinin təhlili ilə kompüterlərin həll edə biləcəyi problemlər dairəsini genişləndirir.[3]
Mürəkkəblik sinifləri müxtəlif məsələlərin həllində istifadə olunan resurs miqdarına görə təsnif olunur. Ən məşhur mürəkkəblik sinifləri aşağıdakılardır:[4]
P (Polinomial vaxt): Bu sinifdəki məsələlər polinomial vaxt çərçivəsində həll edilə bilər. Bu, məsələlərin həllinin praktik olduğunu göstərir. Məsələn, sıralama alqoritmlərinin çoxu P sinifinə aiddir.
NP (ing.Nondeterministic Polynomial Time): Bu sinifdəki məsələlərin həllini yoxlamaq polinomial vaxtda mümkündür, lakin həllini tapmaq eyni dərəcədə asan olmaya bilər. NP məsələlərinə nümunə olaraq "satışmen problemi" (ing.travelling salesman problem) verilə bilər.[5]
NP-tam (ing.NP-complete): Bu sinif NP sinifində olan və eyni zamanda bütün digər NP məsələlərini də polinomial vaxtda çözə bilən məsələləri əhatə edir. Əgər bir NP-tam məsələ P sinifinə aid edilə bilsə, onda bütün NP məsələləri də P-də həll edilə bilər.
NP-çətin (NP-hard): NP-çətin məsələlər NP sinifinə aid olmaya bilər, lakin digər NP məsələlərindən daha az resursla həll edilə bilməz. Bu məsələlər daha genişdir və optimallaşdırma problemlərini də əhatə edir.[6]
P və NP problemi, mürəkkəblik nəzəriyyəsinin ən mühüm açıq suallarından biridir. Problem, P sinifində olan məsələlərin NP sinifində olan bütün məsələlərə bərabər olub-olmadığını öyrənməyə çalışır. Başqa sözlə, "Hər polinomial vaxtda yoxlanıla bilən məsələ polinomial vaxtda həll oluna bilərmi?" sualı ilə bağlıdır. Bu suala cavab verilərsə, hesablama nəzəriyyəsində böyük bir irəliləyiş olar.[7]
Mürəkkəbliyin sərhədləri və Asimptotik Notasiyalar
Mürəkkəblik nəzəriyyəsində problemlərin resurs tələbatını dəyərləndirmək üçün O-Böyük Notasiyası (ing.Big O Notation) və digər asimptotik notasiya üsulları istifadə edilir. Bu, məsələlərin həllində tələb olunan vaxt və yaddaşın nisbətini təsvir edir və alqoritmin "sürətini" ifadə edir.
Məsələn:
O(n): Həll üçün tələb olunan resursların miqdarı giriş məlumatlarının sayı ilə xətti əlaqədədir.
O(n^2): Tələb olunan resurslar giriş məlumatlarının kvadratı ilə əlaqədədir.
Mürəkkəblik nəzəriyyəsi praktiki olaraq bir çox sahədə əhəmiyyətlidir:
Kriptoqrafiya: Çətin həlli olan NP məsələləri (məsələn, böyük ədədlərin sadə ədədlərə bölünməsi) kriptoqrafiya sistemlərinin etibarlılığı üçün əsas yaradır.[8]
Optimizasiya: NP-çətin məsələlər, böyük həcmli verilənləri analiz edərkən effektiv həll yolları tapmağa kömək edir.
Maşın öyrənmə və süni intellekt: Maşın öyrənmə modellərinin mürəkkəbliyini təhlil etməyə imkan verir və bu modellərin təlimində istifadə olunan resursları optimallaşdırır.[9]
Hesablama nəzəriyyəsi müxtəlif modellərlə təchiz edilmişdir və bu modellərdə resurs tələbləri və onların effektivliyi arasında əlaqələr tədqiq edilir. Türinq maşını hesablama modellərinin ən geniş istifadə olunanıdır və mürəkkəblik siniflərini də onun əsasında müəyyənləşdirir.[10]
Mürəkkəblik nəzəriyyəsi kompüter elmlərinin nəzəri əsasını təşkil edir və bu nəzəriyyə ilə alqoritmlərin daha da effektiv şəkildə inkişaf etdirilməsi, məsələlərin həllində lazım olan resursların optimallaşdırılması üçün geniş imkanlar yaradır.[11]