Kas ir algoritmiskā sarežģītība?

Binārās virknes algoritmiskā sarežģītība ir definēta kā īsākā un efektīvākā programma, kas var izveidot virkni. Lai gan ir bezgalīgs skaits programmu, kas var izveidot jebkuru noteiktu virkni, viena programma vai programmu grupa vienmēr būs īsākā. Nav algoritmisks veids, kā atrast īsāko algoritmu, kas izvada noteiktu virkni; šis ir viens no pirmajiem skaitļošanas sarežģītības teorijas rezultātiem. Pat ja tā ir, mēs varam izdarīt saprātīgu minējumu. Šis rezultāts (virknes skaitļošanas sarežģītība) izrādās ļoti svarīgs pierādījumiem, kas saistīti ar aprēķināmību.

Tā kā jebkuru fizisku objektu vai īpašību principā var aprakstīt līdz gandrīz izsmelšanai ar bitu virkni, var teikt, ka objektiem un īpašībām ir arī algoritmiski sarežģīti. Faktiski reālās pasaules objektu sarežģītības samazināšana līdz programmām, kas rada objektus kā izvadi, ir viens no veidiem, kā aplūkot zinātnes uzņēmumu. Sarežģītie objekti mums apkārt mēdz nākt no trim galvenajiem ģenerēšanas procesiem; rašanās, evolūcija un inteliģence, un katra radītie objekti tiecas uz lielāku algoritmisko sarežģītību.

Aprēķinu sarežģītība ir jēdziens, ko bieži izmanto teorētiskajā datorzinātnē, lai noteiktu relatīvās grūtības, kas saistītas ar risinājumu aprēķināšanu plašām matemātisko un loģisko problēmu klasēm. Pastāv vairāk nekā 400 sarežģītības klases, un nepārtraukti tiek atklātas papildu klases. Slavenais P = NP jautājums attiecas uz divu no šīm sarežģītības klasēm. Sarežģītības klases ietver problēmas, kas ir daudz grūtākas nekā jebkas, ar ko varētu saskarties matemātikā līdz pat aprēķiniem. Aprēķinu sarežģītības teorijā ir daudz iedomājamu problēmu, kuru atrisināšanai būtu nepieciešams gandrīz bezgalīgs laiks.

Algoritmisko sarežģītību un ar to saistītās koncepcijas 1960. gados izstrādāja desmitiem pētnieku. Andrejs Kolmogorovs, Rejs Solomonovs un Gregorijs Čaitins sniedza nozīmīgu ieguldījumu 60. gadu beigās ar algoritmiskās informācijas teoriju. Minimālā ziņojuma garuma princips, kas ir cieši saistīts ar algoritmisko sarežģītību, nodrošina lielu daļu statistisko un induktīvo secinājumu un mašīnmācīšanās pamatu.