A költséghatékony kampányutak titkai - avagy hogyan nyerjünk 1 millió dollárt
Az utóbbi év egyik legfontosabb világpolitikai eseménye volt az amerikai elnökválasztás – a szavazók dönthettek arról, hogy kire bízzák a Föld egyik legerősebb országának vezetését. Egy kampány sikerét a győzelmen kívül azonban az is meghatározza, mennyire lesz az költséghatékony - például, hogy milyen útvonalon járjuk be a legfontosabb választói kerületeket. Ezzel foglalkozik a matematika egyik legnépszerűbb megoldatlan kérdése, a P=NP probléma.
David Hilbert matematikus 1900-as, Sorbonne-on tartott előadásában huszonhárom megoldatlan problémát vázolt fel, melyek nagyban befolyásolták a következő évszázad matematikai érdeklődésének alakulását. A nagy hatású hilberti problémák analógiájára 2000-ben a Clay Mathematics Institute újabb hét problémát tett közzé. Ezek többségének már a megértéséhez is komoly matematikai előképzettség szükséges, ugyanakkor a P=NP probléma meglepően egyszerűen elmagyarázható.
A számítógépek korlátai
Az utóbbi években az informatika térnyerésével egyre több olyan kérdésre is meg tudjuk mondani a választ, amelyek megválaszolása korábban jóval több időt, akár hosszú éveket vett volna igénybe. Ugyanakkor még mindig jócskán akadnak olyan problémák, amelyekre a választ csak hosszú napok, esetleg évek alatt adhatják meg a szuperszámítógépek. Az egyik ilyen nehéznek számító kérdés az utazóügynök-probléma.
Az utazóügynök-probléma
Tegyük fel, hogy egy vállalat ügynökei vagyunk, és az a feladatunk, hogy felkeressük az ország összes városát. Szerencsére adott egy térképünk, így előre megtervezhetjük az utunkat. A kérdés, hogy milyen útvonalon induljunk el úgy, hogy a legkevesebbet kelljen utazni, de minden várost érintenünk kell. Az elsőre egyszerűnek tűnő problémára máig nem ismert gyors algoritmus – például csupán 2004-ben sikerült Svédország összes városára megválaszolni a kérdést.
Gyors algoritmus: a matematikában a polinomiális időben futókat szokás ide sorolni. Ez azt jelenti a példánkban, hogyha van ’n’ darab városunk, akkor az algoritmus idejének kiszámolásához ’n’-et csak szorozni, illetve összeadni kell párszor. A lassú algoritmusoknak az exponenciálisakat szokás nevezni, amiknél valamilyen számot kell az ’n’-edik hatványra emelni. Összehasonlításként, ha a két futási idő n*n (gyors) és 2^n (lassú) és n=10 városunk van, akkor az első esetben 100 lesz az idő, míg a másodiknál 1024 – nagyobb ’n’-ekre ezek még inkább különböznek.
A millió dolláros kérdés
A P=NP probléma fő kérdése, hogy lehet-e a nehéz problémákra (ezeket szokás NP-belieknek hívni) gyors algoritmust adni (ezeket nevezik P-belieknek). A legtöbb matematikus szkeptikus a kérdésben, mivel ez eddig még senkinek se sikerült. A kérdés azonban nyitott, így bárki próbálkozhat ilyenek keresésével – az is motiváló lehet, hogy a Clay Mathematics Institute a megoldónak egymillió dolláros pénzjutalmat ígér.
Források:
Pierre Basieux (2007): Top 7 - Az ezredforduló legkihívóbb matematikai problémái. Typotex, 2007.
