Mi az algoritmikus bonyolultság?
Algoritmikus bonyolultság (számítási komplexitás vagy Kolmogorov komplexitás) alapvető ötlet mind a számítási komplexitás elméletében és algoritmikus információelmélet , és fontos szerepet játszik a formális indukcióban.
A bináris karakterlánc algoritmikus összetettségét a legrövidebb és leghatékonyabb programnak tekintik, amely képes előállítani a karakterláncot.Noha van egy végtelen számú program, amely képes előállítani az adott karakterláncot, az egyik program vagy a programcsoport mindig a legrövidebb.Nincs algoritmikus módszer a legrövidebb algoritmus megtalálására, amely egy adott karakterláncot ad ki;Ez a számítási komplexitás elméletének egyik első eredménye.Ennek ellenére képzett kitalálást is tehetünk.Ez az eredmény (a karakterlánc számítási bonyolultsága) nagyon fontosnak bizonyul a kiszámíthatósághoz kapcsolódó bizonyítékok szempontjából.Azt mondhatjuk, hogy algoritmikus bonyolultsággal is rendelkeznek.Valójában a valós objektumok bonyolultságának csökkentése olyan programokra, amelyek objektumokat eredményeznek kimenetként, az egyik módja a tudomány vállalkozásának megtekintésének.A körülöttünk lévő komplex tárgyak általában három fő generációs folyamatból származnak;
kialakulás, evolúció és intelligencia , az egyes objektumok által előállított objektumokkal, amelyek a nagyobb algoritmikus komplexitás felé mutatnak.matematikai és logikai problémák.Több mint 400 komplexitási osztály létezik, és további osztályokat fedeznek fel.A híres P ' NP kérdés e bonyolultsági osztályok közül két természetére vonatkozik.A bonyolultsági osztályok sokkal nehezebb problémákat tartalmaznak, mint bármi más, amellyel a matematikában a kalkulusig szembesülhetnek.Számos elképzelhető probléma merül fel a számítási komplexitás elméletében, amelyhez a megoldáshoz közel infinite idő szükséges.
Az algoritmikus összetettség és a kapcsolódó fogalmak az 1960-as években tucatnyi kutató fejlesztette ki.Andrey Kolmogorov, Ray Solomonoff és Gregory Chaitin a 60 -as évek végén fontos hozzájárulást nyújtott az algoritmikus információelméletben.A minimális üzenethossz elve, amely szorosan kapcsolódik az algoritmikus bonyolultsághoz, a statisztikai és induktív következtetések és a gépi tanulás alapjainak nagy részét biztosítja.