Thesis supervisor: Dániel Marx
belső konzulens: Lajos Rónyai
Location of studies (in Hungarian): MTA SZTAKI, Algebra Tanszék Abbreviation of location of studies: BME
Description of the research topic:
A gyakorlatban felmerülő algoritmikus problémák jelentős része NP-nehéz, így ezekre nem várhatunk polinomidejű algoritmust. Ha meg kívánjuk oldani ezeket a problémákat, akkor ez mindenképpen csak exponenciális futási idejű algoritmussal történhet, de nagyon nem mindegy, hogy a futási idõ miben exponenciális. A paraméteres bonyolultságelmélet célja az, hogy a futási idõ exponenciális növekedését a probléma valamilyen jól meghatározott jellemzőjére korlátozzuk. Így nagy méretű problémákra is hatékony algoritmust tudunk adni, ha ezen paraméter értéke kicsi.
Példaként tekintsük a maximális klikk és a minimális lefogó ponthalmaz problémákat. Ha azt kívánjuk eldönteni, hogy létezik-e k méretű klikk egy n csúcsú gráfban, akkor ezt megtehetjük az O(n^k) eset végigpróbálásával. Rögzített k esetén ez egy polinom idejű algoritmust ad, de ez a módszer teljesen használhatatlan már pl. n=100 és k=10 esetén is. Hasonlóan, az összes eset vizsgálatával a minimális lefogó csúcshalmaz problémát is meg tudjuk oldani O(n^k) próbálkozással. Viszont itt lényegesen jobb, O(kn+1.2852^k) idejű algoritmus is ismert. Ez az algoritmus hatékonyan működik pl. k=50 esetén bármilyen ésszerű méretű n mellett.
A kulcskérdés az, hogy a futási időben a k paraméter ne forduljon elő az n kitevőjében, mert akkor az n növelésével a futási idő robbanásszerűen növekszik, még kis k érték esetén is. A paraméteres bonyolultságelmélet központi fogalma az uniform polinomiális algoritmus, ami azt jelenti, hogy a futási idő f(k)* n^c valamilyen csak k-tól függő függvényre és c konstansra. A minimális lefogó ponthalmazhoz hasonlóan számos NP-nehéz problémára létezik uniform polinomiális algoritmus. Az ilyen algoritmusok konstruálása egyáltalán nem triviális, sokszor rendkívül érdekes és mély kombinatorikai eszközök kerülnek elő.
Az NP-teljesség elméletéhez hasonlóan a paraméteres bonyolultság is rendelkezik egy negatív eszköztárral, amellyel a nehéz problémákat azonosíthatjuk. Azzal, hogy egy problémáról igazoljuk, hogy W[1]-nehéz, azt bizonyítjuk, hogy (a szokásos bonyolultságelméleti feltételezések mellett) a problémára nem adható uniform polinomiális algoritmus.
A leglényegesebb technikák megismerése után a jelölt feladata önálló eredmények elérése a paraméteres problémák vizsgálata terén. Ez azt jelenti, hogy uniform polinomiális algoritmusok konstruálásával illetve teljességi eredmények bizonyításával kell az egyes problémák, problémaváltozatok bonyolultságát meghatározni. A tématerület viszonylagos fiatalsága miatt még számos alapvető nyitott kérdés vár megválaszolásra, így sok lehetőség nyílik új eredmények elérésére. Igény esetén lehet foglalkozni egy konkrét alkalmazási területhez kapcsolódó problémákkal, vagy az algoritmusok gyakorlatban történő alkalmazásának a hatékonyságával.
Szakirodalom:
1. Downey, Fellows: Parameterized Complexity. Springer, 1999.
2. Niedermeier: Invitation to fixed-parameter algorithms. Oxford, 2006.
3. Flum, Grohe: Parameterized Complexity Theory. Springer, 2006.
Required language skills: angol Further requirements: Mérnöki vagy TTK-s, jó vagy kiváló minősítésű diploma. Angol nyelvismeret.
Number of students who can be accepted: 1
Deadline for application: 2014-05-31
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Login
