Algoritmusok bonyolultsága

Előszó

Az az igény, hogy egy feladat, algoritmus vagy struktúra bonyolultságát számszerűen mérni tudjuk, és ennek alapján e bonyolultságra korlátokat és számszerű összefüggéseket nyerjünk, egyre több tudományág területén vetődik fel: a számítógéptudományon kívül a matematika hagyományos ágai, á statisztikus fizika, a biológia, az orvostudomány, a társadalomtudományok és a mérnöki tudományok is egyre gyakrabban kerülnek szembe ezzel a kérdéssel. A számítógéptudomány ezt a problémát úgy közelíti meg, hogy egy feladat elvégzéséhez szükséges számítástechnikai erőforrások (idő, tár, program, kommunikáció) mennyiségével méri a feladat bonyolultságát. Ennek az elméletnek az alapjaival foglalkozik ez a jegyzet.
A bonyolultságelmélet alapvetően három különböző jellegű részre oszlik. Először is, be kell vezetni az algoritmus, idő, tár stb. pontos fogalmát. Ehhez a matematikai gép különböző modelljeit kell definiálni, és az ezeken elvégzett számítások tár- és időigényét tisztázni (ezt általában a bemenet méretének függvényében mérjük). Az erőforrások korlátozásával a megoldható feladatok köre is szűkül; így jutunk a különböző bonyolultsági osztályokhoz. A legalapvetőbb bonyolultsági osztályok a matematika klasszikus területein felvetődő problémáknak is fontos, és a gyakorlati és elméleti nehézséget jól tükröző osztályozását adják. Ide tartozik a különböző modellek egymáshoz való viszonyának vizsgálata is.
Másodszor, meg kell vizsgálni, hogy a legfontosabb algoritmusok a matematika különböző területein milyen erőforrás-igényűek, ill. hatékony algoritmusokat kell megadni annak igazolására, hogy egyes fontos feladatok milyen bonyolultsági osztályokba esnek. Ebben a jegyzetben a konkrét algoritmusok ill. feladatok vizsgálatában nem törekszünk teljességre; ez az egyes matematikai tárgyak (kombinatorika, operációkutatás, numerikus analízis, számelmélet) dolga.
Harmadszor, módszereket kell találni „negatív eredmények" bizonyítására, vagyis annak igazolására, hogy egyes feladatok nem is oldhatók meg bizonyos erőforráskorlátozások mellett. Ezek a kérdések gyakran úgy is fogalmazhatók, hogy a bevezetett bonyolultsági osztályok különbözőek-e ill. nem üresek-e. Ennek a problémakörnek része annak a vizsgálata, hogy egy feladat megoldható-e egyáltalán algoritmikusán; ez ma már klasszikus kérdésnek tekinthető és sok fontos eredmény van vele kapcsolatban. A gyakorlatban felvetődő algoritmikus problémák többsége azonban olyan, hogy algoritmikus megoldhatósága önmagában nem kérdéses, csak az a kérdés, hogy milyen erőforrásokat kell ehhez felhasználni. Az ilyen alsó korlátokra vonatkozó vizsgálatok igen nehezek és még gyerekcipőben járnak. Ebben a jegyzetben is csak Ízelítőül tudunk bemutatni néhány ilyen jellegű eredményt. Vissza