Hesablama mürəkkəbliyi nəzəriyyəsi

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]

Əsas mövzuları

Mürəkkəblik sinifləri

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]

1. 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.
2. 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]
3. 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.
4. 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

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əsinin tətbiqləri

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]

Türinq maşını illüstrasiya

Hesablama modelleri və mürəkkəblik teoremləri

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]

İstinadlar

1. Zobel, Justin. Writing for Computer Science. Springer. 2015. səh. 132. ISBN 978-1-44716639-9.
2. "P vs NP Problem | Clay Mathematics Institute". www.claymath.org (ingilis). July 6, 2018 tarixində orijinalından arxivləşdirilib. İstifadə tarixi: July 6, 2018.
3. See Arora, Barak, 2009, Chapter 1: The computational model and why it doesn't matter
4. Berger, Bonnie A.; Leighton, T, "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete", Journal of Computational Biology, 5 (1), 1998: 27–40, CiteSeerX 10.1.1.139.5547, doi:10.1089/cmb.1998.5.27, PMID 9541869.
5. Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) Introduction to Automata Theory, Languages, and Computation, Addison Wesley, Boston/San Francisco/New York (page 368)
6. Jaffe, Arthur M., "The Millennium Grand Challenge in Mathematics" (PDF), Notices of the AMS, 53 (6), 2006, 2006-06-12 tarixində arxivləşdirilib (PDF), İstifadə tarixi: 2006-10-18.
7. Schöning, Uwe, "Graph Isomorphism is in the Low Hierarchy", Journal of Computer and System Sciences, 37 (3), 1988: 312–323, doi:10.1016/0022-0000(88)90010-4
8. Arvind, Vikraman; Kurur, Piyush P., "Graph isomorphism is in SPP", Information and Computation, 204 (5), 2006: 835–852, doi:10.1016/j.ic.2006.02.002.
9. Fortnow, Lance. "Computational Complexity Blog: Factoring". weblog.fortnow.com. 2002-09-13. 2008-11-19 tarixində arxivləşdirilib. İstifadə tarixi: 2024-10-29.
10. Wolfram MathWorld: Number Field Sieve Arxiv surəti 12 iyul 2018 tarixindən Wayback Machine saytında
11. Boaz Barak's course on Computational Complexity Arxiv surəti 10 may 2024 tarixindən Wayback Machine saytında Lecture 2 Arxiv surəti 10 may 2024 tarixindən Wayback Machine saytında

Dərsliklər

• Arora, Sanjeev; Barak, Boaz, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, ISBN 978-0-521-42426-4, Zbl 1193.68112
• Downey, Rod; Fellows, Michael, Parameterized complexity, Monographs in Computer Science, Berlin, New York: Springer-Verlag, 1999, ISBN 9780387948836
• Du, Ding-Zhu; Ko, Ker-I, Theory of Computational Complexity, John Wiley & Sons, 2000, ISBN 978-0-471-34506-0
• Goldreich, Oded, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008
• van Leeuwen, Jan, redaktorHandbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, 1990, ISBN 978-0-444-88071-0
• Khalil, Hatem; Ulery, Dana, A review of current studies on complexity of algorithms for partial differential equations // Proceedings of the annual conference on - ACM 76, 1976, 197–201, doi:10.1145/800191.805573, ISBN 9781450374897
• Papadimitriou, Christos, Computational Complexity (1st), Addison Wesley, 1994, ISBN 978-0-201-53082-7
• Sipser, Michael, Introduction to the Theory of Computation (2nd), USA: Thomson Course Technology, 2006, ISBN 978-0-534-95097-2