Shkencëtari kompjuterik thotë se ka zgjidhur problemin matematikor P vs NP

[vaaldr1n]

Vinay Deolalikar, i cili punon në dorën hulumtuese të Hewlett-Packard në Palo Alto, Kaliforni beson se ai ka zgjidhur gjëegjëzën e P vs NP, në një lëvizje që mund të transformojë përdorimin e kompjuterit nga njeriu dhe gjithashtu mund t’i sjellë atij një çmim prej 1 milion dollarë.
P vs NP është një prej shtatë problemeve të mileniumit të vendosura nga Institutit Matematikor i Clay me bazë në Massachusetts, dhe cilësohet si më i “vështiri” për tu zgjidhur.

Në të përfshihen shumë llogaritje matematikore duke përfshirë kontrollimin e një numri të madh të zgjidhjeve të mundshme që janë përtej aftësive të tanishme të cilido kompjuter. Megjithatë, përgjigjet për disa janë të shpejta dhe të lehta për tu verifikuar si të sakta. P vs NP konsideron nëse ka një mënyrë për të arritur tek përgjigjet e llogaritjeve në një mënyrë më të shpejtë.

z. Deloalikar pretendon të ketë vërtetuar se P, që i referohet Problemit zgjidhja e të cilit mund të gjendet me lehtësi dhe të verifikohet, nuk është e njëjtë me Np, që i referohet problemeve zgjidhjet e të cilave janë pothuajse të pamundshme por që mund të verifikohen me lehtësi. Letra e tij që u postua të premten, tani po shikohet në detaje nga shkencëtarët kompjuterik.

Scott Aaronson, një asistent profesor i shkencave kompjuterike pranë Institutit Maassachusetts të Teknologjisë, është aq skeptik sa që ka premtuar në blogun e tij edhe 200.000 dollarë shtesë për z. Deloalikar nëse zgjidhja pranohet nga Clay. Ai shkroi se “nëse P#Np është vërtetuar, atëherë kjo do të ndryshojë jetën time në mënyrë dramatike sa që pagesa prej 200.000 dollarë do të jetë më e pakta që do të mund të bëjë”.

Problemi P vs N\p ishte formalizuar në vitin 1971 nga matematicentët Stephen Cock dhe Leonid Levin. Për të ndihmuar në kuptimin e çështjes, Instituti Matematikor i Clay ofron një shembull në llogaritje si të akomodohen 400 studentë në 100 dhoma të universitetit. Aty thuhet: “Për të komplikuar çështjet, Dekani të ka ofruar ty një listë me palët e studentëve të papërshtatshëm dhe ka kërkuar që asnjë palë nga lista të paraqitet në zgjidhjen tuaj finale”.

”Ky është një shembull i asaj që shkencëtarët kompjuterik e quajnë problem NP, qpasi që është lehtë të kontrollohet nëse një zgjidhje e dhënë prej 100 studentëve të propozuar nga një bashkëpunëtorë është e kënaqshme, megjithatë detyra e gjenerimit të një liste të këtillë nga zero, duke aq e vështirë sa që duket të jetë tërësisht jo praktike”.

”Në fakt, numri total i mënyrave të zgjedhjes së njëqind studentëve prej 400 aplikantëve është më i madh se numri i atomeve në universin e njohur”.

”Shkenca kompjuterike po dëshiron të përcaktojë nëse ekziston pyetja përgjigja e të cilës mund të kontrollohet me lehtësi por që nuk kërkon një periudhë të gjatë pafundësisht për të zgjidhur çfarëdo procedure të drejtpërdrejtë”.