összetettségelmélethez

Az összetettségelmélet a számítógéptudomány azon ága, amely a problémák megoldásához szükséges idő- és memóriaigények alakulását vizsgálja, különösen a legrosszabb esetekben és az aszimptotikus viselkedésben.

Fő fogalmai közé tartoznak a számítási modellek és az osztályok, mint a P, NP, co-NP, PSPACE és EXP, valamint a polinomiális idő alatt végrehajtható redukciók fogalma, amelyek megmutatják, hogy egy problémát hogyan lehet átalakítani egy másikba.

A döntési problémák területén kiemelkedő eredmény a Cook–Levin tétel, amely megmutatja, hogy a SAT egy NP–teljes problémát jelent. Ennek következtében sok más NP-probléma polinomiális idő alatt redukálható rá. Például a döntési változata a Traveling Salesman problémának NP-complete.

A teória foglalkozik továbbá a véletlenszerűség hatásaival (például az RP és a BPP osztályok) és a determinisztikus–nem-determinisztikus memóriaigény viszonyával, valamint a PSPACE-alapú eredményekkel. A P vs NP nyitott kérdés a legfontosabb példát jelenti.

Jelenleg az összetettségelmélet alapvető hatást gyakorol a számítógépes algoritmusok tervezésére, a kriptográfiára és a teoretikus számítástudományra. A nehéz problémák megértése segíti a gyakorlati megoldási stratégiák kiválasztását és a számítási nehézség elméleti megközelítéseinek kidolgozását.

A terület nyitott témái közé tartozik a különböző komplexitási osztályok közötti pontos kapcsolatok tisztázása, a redukciók alkalmazásának szélesítése, és a kvantumszámítás vagy más modellek hatásának vizsgálata.