komplexitáselméletek

A komplexitáselméletek a komplex rendszerek viselkedésének és szerkezetének megértésére irányuló elméleti és módszertani keretek összessége. A kifejezés több hagyományt is magába foglal: egyrészt a számítástechnikai komplexitáselméletet, amely az algoritmusok erőforrásigényét vizsgálja, másrészt a komplex rendszerek elméletét, amely a nemlineáris kölcsönhatásokból adódó viselkedési mintákat és szerkezeti tulajdonságokat elemzi.

Számítástechnikai oldalról a komplexitás az algoritmusok futási idejének és memóriaigényének aszimptotikus növekedését vizsgálja bemeneti méret függvényében. Alapvető kategóriák közé tartozik a P, az NP és az NP-teljes (NP-complete) problémák; vannak NP-hard feladatok is. A redukciók segítségével lehet megítélni egy probléma nehézségét, és megérteni a közöttük fennálló összefüggéseket. A klasszikus vizsgálatok közé tartozik a döntési feladatok megoldhatósága és a legrosszabb vagy átlagos esetekre vonatkozó nehézség.

Az algoritmikus információelmélet vagy Kolmogorov-komplexitás egy adott bemenet legrövidebb leírásának hosszát méri. Ezzel a nézőponttal a komplexitás az információ tartalmától is függ, nem csak a gyakoriságoktól. A terület fontos hozzájárulói közé tartoznak Kolmogorov, Chaitin és Solomonoff, akik az adatok leírási hosszának elméleti korlátait vizsgálták.

A komplex rendszerek elmélete a lokális interakciókból származó emergens viselkedést vizsgálja. Ide tartoznak a nemlineáris dinamika, az önszerveződés, a kölcsönös visszacsatolások és a hálózati struktúrák hatásai a robusztusságra és az adaptációra. Jellemző jelenségek közé tartozik a kritikus állapotok, a skálázódás és hosszú távú függőségek.

Kutatási módszerek közé tartozik a matematikai modellezés, számítógépes szimulációk (ügynökalapú modellek, celluláris automaták) és hálózatelemzés. Alkalmazási területek széles skálán: informatika, fizika, biológia, közgazdaságtan és a társadalomtudományok, valamint infrastrukturális rendszerek elemzése.