Računalniški problem tisočletja

Eden izmed šestih problemov tisočletja je tudi računalniški problem P proti NP problem. Sprašuje nas ali lahko računalnik hitro preveri pravilnost rešitve, ali je potem tudi hitro rešljiv? Mogoče se vprašanje ne sliši tako zapleteno, a dokazal ga do zdaj ni še nihče.

Opis problema:

Razložimo problem bolj podrobno. Črka P označuje razred problemov, ki so rešljivi v polinomskem času. Torej čas njihovega reševanja variira kot polinomska funkcija. Obstajajo pa problemi, katerih rešitev računalniki ne morejo pridobiti hitro, lahko pa enostavno preverijo pravilnost vnaprej podane rešitve. Takšni spadajo v razred  NP, kjer kratica označuje nedeterministični polinomski čas. Iz tega sledi, da so vsi P problemi tudi NP problemi, torej če so lahko rešljivi, jih je lahko tudi preveriti. Ali potem vedno velja P = NP? Ravno to si vsi prizadevajo dokazati.

Poglejmo si primer iz resničnega življenja. Popotnik želi z avtom obiskati 100 različnih mest, z začetnim in končnim krajem pri njem doma. Težava pa je v tem, da ima omejeno količino goriva in lahko prevozi največ 10 000 km. Zanima ga ali lahko obišče vsa mesta brez, da bi mu zmanjkalo goriva. Problem je težko rešljiv, ampak rešitev obstaja. Samo iti moramo skozi vse možne poti. Preverjanje pravilnosti, ko imamo enkrat rešitev pa za računalnik ni težko. Tukaj vidimo problematiko tovrstnih problemov.

Kaj pa ljudi tako vleče, da bi končno dokazali, da  P = NP enakost velja? Z dokazom bi precej poenostavili računalniško reševanje težko rešljivih problemov iz realnosti. Poleg pa lahko tudi obogatiš, saj ti matematični inštitut Clay (Oxford) podari milijon dolarjev.

Spodaj si lahko ogledate video, ki problem še bolj pojasni.

VIRI:

Komentarji
Ingrid Mirnik

Ingrid Mirnik

Ingridine sanje so, da bi se njeno sklanjano ime slišalo normalno.
Navdušuje se nad tehnologijo, športom, psihologijo, sladicami, kavo, hribi, lepimi razgledi, vesoljem,v bistvu nad vsem kar niso špageti.
Je odvisnica od športa, ki ji nikdar ne zmanjka energije. Do cilja pa jo vleče moto: »Hitreje delam, hitreje končam, hitreje bom jedla.«
Ingrid Mirnik

Latest posts by Ingrid Mirnik (see all)

Ingrid Mirnik

Ingridine sanje so, da bi se njeno sklanjano ime slišalo normalno. Navdušuje se nad tehnologijo, športom, psihologijo, sladicami, kavo, hribi, lepimi razgledi, vesoljem, v bistvu nad vsem kar niso špageti. Je odvisnica od športa, ki ji nikdar ne zmanjka energije. Do cilja pa jo vleče moto: »Hitreje delam, hitreje končam, hitreje bom jedla.«