Miklós
-7 °C
2 °C

Az egymillió dolláros aknakereső

2000.11.03. 17:44
Richard Kaye, a birminghami egyetem matematikusa az ismert számítógépes játék, az aknakereső segítségével megoldhat egy harminc éves matematikai problémát, amelynek megfejtésére egymillió dolláros díjat tűztek ki.

Az aknakereső (angol nevén: minesweeper), már legalább egy évtizede édestestvére a pasziánsznak és a fekete macskának a Windows kellékei között. Az ideggyilkolásra alkalmazott játék létjogosultságát bizonyítja, hogy Richard Kaye matematikus általa oldhat meg egy három évtizede megoldatlan 'P versus NP'problémát.

Aknamentesítés kezdőknek

Az aknakereső egyszerű, de nehéz játék. A kiindulópont egy teljesen sima négyzetrácsos mező, amelyben bármely négyzet alatt akna rejtőzhet - ha aknára kattintunk, az felrobban, és a játékot elvesztettük. Az olyan négyzet, amelyben nincs akna, kattintás után megjelentik egy szám, amely megmutatja, hogy a körülötte található nyolc négyzetben összesen hány akna található. Ha tehát a számokból elég okosan következtetünk, hogy hol van akna és hol nincs, feltérképezhetjük az egész aknamezőt: Ez pedig győzelem.

P vagy nem P?

A 'P avagy NP' probléma a matematikai feladatok megoldhatóságával kapcsolatos kérdés - egészen pontosan arról szól, hogy a kettő valójában különböző vagy ugyanaz. Az elvárt válasz adott: különbözőek, de ezt eddig nem sikerült bebizonyítani.

Az AND függvény ábrázolása aknakeresőben
A P egy olyan problémát jelöl amely polinomiális, vagyis megoldása egy adott számítási módszerrel mindig ugyanannyi időt vesz igénybe - mondjuk egy adatbázisban tízszer annyi tétel szortírozása tízszer annyi időt vesz igénybe.

A non-P probléma alapvetően egy P-nél nehezebb probléma, amelynek nincs adott időn belül tuti megoldása. A non-P probléma létezését az tudja bebizonyítani, aki nekiül és az összes lehetséges számítási módszert végigpróbálgatva állítja, hogy egyik sem polinomiális, és nem hullik el közben végelgyengülés miatt. Eddig senkinek sem sikerült.

A non-P gyanúsított problémák egy csoportját NP-nek nevezzük (nondeterminisztikus-P, avagy fogalmunksincs-P). Az NP olyan probléma, amelynél meg tudjuk állapítani, hogy megoldása P. Ezen belül van még egy kisebb csoport, amelyet NP-teljes problémáknak nevezünk - ezek olyanok, amelyekhez egyetlen polinomiális megoldás kulcs lenne minden NP-hez.

Amennyiben tehát egy NP-teljes problémának P megoldása akad, minden NP P-nek bizonyulna. A feltevés az, hogy mivel ilyen megoldás nincs, minde NP-teljes probléma non-P.

Az idő, méret

A 'P avagy NP' probléma eldöntése a gyakorlatban azt jelenti, hogy egy feladatról megállapítható-e, hogy ésszerű időn belül megoldhatja-e mondjuk egy számítógép.

Richard Kaye gyermekeivel
Kaye észrevette, hogy amíg egy tízszer tízes aknakeresőt lagymatag állapotban egy percen belül meg tud oldani, egy százszor százasat már rendkívül hosszú idő alatt sem.

,,Mindig érdekeltek az olyan játékok, amelyekben van matematika. A matematika és a játékok remekül illenek egymáshoz" - mondja Kaye - ,,Észrevettem, hogy egy nagyon szép matematika lapul mögötte, de nem tudtam, mit keresek."

A 'P versus NP' probléma közel harminc éves. Aki megoldja, arra nagy öröm vár, hiszen az amerikai Clay Matematikai Intézet - természetesen szigorú bizonyítási feltételek mellett - egymillió dollárt ajánl fel a helyes megoldás beküldőjének.

Richard Kaye egylőre nem milliomos, mindössze arra jött rá, hogy az aknakereső működési megoldási mechanizmusa és annak sajátosságai kulcsfontosságúak lehetnek a megoldás szempontjából. Mennyi időbe kerül egyetlen egy aknát megtalálni egy végtelen aknamezőn. Aki kitalálja könnyedén feltörheti majd az eddig biztonságosnak hitt kódrendszereket.