Senda inn spurningu
Sólin Sólin Rís 05:19 • sest 21:35 í Reykjavík
Tunglið Tunglið Rís 25:18 • Sest 04:56 í Reykjavík
Flóð Flóð Árdegis: 07:07 • Síðdegis: 19:24 í Reykjavík
Fjaran Fjara Árdegis: 01:08 • Síðdegis: 13:14 í Reykjavík
Visit the English version

Flokkun:

Náttúruvísindi og verkfræði Tölvunarfræði

Hvað felst í vandamálinu ,,P vs. NP''?

Erlendur S. Þorsteinsson

Skýrum fyrst um hvað spurningin snýst. Til einföldunar má segja að hún varði afköst eða getu tölva til að leysa tiltekin verkefni. Það er þó ekki svo einfalt að þetta snúist um hvað tölvan geti framkvæmt margar aðgerðir á sekúndu heldur frekar hvað þurfi margar aðgerðir eða skref til að leysa tiltekið vandamál.

Verkefnum sem hægt er að leysa með aðstoð tölvu er raðað í flokka eftir því hve erfið þau eru, nánar tiltekið eftir því hvað talið er að þurfi margar aðgerðir til að leysa þau. Slíkt mat er auðvitað háð því að fundist hafi hagkvæmasta reikniritið (e. algorithm), eða aðferðin, til að leysa tiltekið verkefni. Um reiknirit, sem einnig kallast algrím, má lesa í svari Snorra Agnarssonar við spurningunni Hvað er algrím og hvernig nýtist það í tölvufræði?

Þessir hópar verkefna eru kallaðir flækjustigsflokkar. Einn af þeim er kallaður P og í honum eru öll verkefni sem hægt er að leysa með fjölda aðgerða sem er í stærðarþrepi (stærðargráðu, order of magnitude) margliðu miðað við stærð inntaksins. Til dæmis ef inntakið er strengur af lengd n þá væri verkefni sem leysa má með n2 aðgerðum í flokknum P en verkefni sem þarf 3n aðgerðir væri ekki í P (af því að fallið 3n er ekki margliða í n). Annar hópur er kallaður NP og í honum eru öll verkefni þar sem hægt er að staðfesta uppgefna lausn með fjölda aðgerða sem er af margliðustærðargráðu miðað við stærð inntaksins.

Í P eru vandamál eins og línuleg bestun, að finna stærsta samnefnara og að ákvarða hvort að tala er prímtala eða ekki. Þessi vandamál eru einnig í NP en til viðbótar er talið að þáttun tölu, ferðasölumannsvandamálið, netlitunarvandamálið og mörg fleiri verkefni séu í NP en ekki í P.

Tengsl flækjustigsflokkana P og NP er enn óleyst vandamál. Það er vitað að P er hlutmengi í NP því ein leið til að staðfesta hvort að tiltekin lausn á verkefni sé rétt er einfaldlega að leysa verkefnið aftur og fá sömu lausn. En það er ekki vitað hvort P og NP séu í raun sama mengið eða sami hópur verkefna. Til einföldunar má segja að spurningin sem þurfi að svara sé ,,er til verkefni þar sem tiltölulega auðvelt er að staðfesta að uppgefin svör séu rétt en mjög erfitt er að finna rétt svör?'' þar sem ,,mjög erfitt" þýðir að hraðvirk tölva gæti verið milljónir ára að leita að réttri lausn með besta reikniritinu sem til væri, en án árangurs. Innifalið í spurningunni er að sýna þarf fram á að ekkert betra reiknirit gæti verið til, það er að segja að vandamálið við að finna lausn á hagkvæman hátt sé ekki skortur á hugmyndaflugi við að uppgötva gott reiknirit heldur sú staðreynd að slíkt hagkvæmt reiknirit sé alls ekki til.

Þessi spurning, ,,er P = NP?'', er ein sú mikilvægasta í tölvunarfræði og hefur til dæmis Clay Mathematics stofnunin boðið eina milljón Bandaríkjadala í verðlaun fyrir rétta lausn.

Svarið við þessari spurningu myndi hafa mikil áhrif á tölvunarfræði, sérstaklega ef niðurstaðan væri sú að P og NP sé sama mengið. Einkum hefði það áhrif á dulmálsfræði, en í dulritun eru notuð verkefni sem vitað er að eru í NP en talið er að séu ekki í P (auðvelt að afkóða ef lykill er til staðar en ómögulegt að brjóta upp dulkóðun án lykils). Ef í ljós kæmi að P og NP er sama mengið þá væri þar með hægt að brjóta upp alla þá dulritun sem notuð er í dag, til dæmis í netbankaviðskiptum, án þess að vera með réttan lykil.

Upphaflega spurningin var:

Getið þið skýrt út fyrir mér hvað felst í stærðfræðivandamálinu ,,P vs. NP'' (sem er eitt af þúsaldarvandamálum Clay-stofnunarinnar)?

Frekara lesefni af Vísindavefnum:

Heimildir

Höfundur

Erlendur S. Þorsteinsson

reiknifræðingur

Útgáfudagur

23.6.2008

Spyrjandi

Einar Óli Guðmundsson
Úlfur Bragi Einarsson, f. 1993

Efnisorð

Tilvísun

Erlendur S. Þorsteinsson. „Hvað felst í vandamálinu ,,P vs. NP''?“ Vísindavefurinn, 23. júní 2008. Sótt 25. apríl 2024. http://visindavefur.is/svar.php?id=19121.

Erlendur S. Þorsteinsson. (2008, 23. júní). Hvað felst í vandamálinu ,,P vs. NP''? Vísindavefurinn. Sótt af http://visindavefur.is/svar.php?id=19121

Erlendur S. Þorsteinsson. „Hvað felst í vandamálinu ,,P vs. NP''?“ Vísindavefurinn. 23. jún. 2008. Vefsíða. 25. apr. 2024. <http://visindavefur.is/svar.php?id=19121>.

Chicago | APA | MLA

Þessi síða notar vafrakökur Nánari upplýsingar

Ég samþykki
Spyrja

Sendu inn spurningu LeiðbeiningarTil baka

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=

Senda grein til vinar

=

Hvað felst í vandamálinu ,,P vs. NP''?
Skýrum fyrst um hvað spurningin snýst. Til einföldunar má segja að hún varði afköst eða getu tölva til að leysa tiltekin verkefni. Það er þó ekki svo einfalt að þetta snúist um hvað tölvan geti framkvæmt margar aðgerðir á sekúndu heldur frekar hvað þurfi margar aðgerðir eða skref til að leysa tiltekið vandamál.

Verkefnum sem hægt er að leysa með aðstoð tölvu er raðað í flokka eftir því hve erfið þau eru, nánar tiltekið eftir því hvað talið er að þurfi margar aðgerðir til að leysa þau. Slíkt mat er auðvitað háð því að fundist hafi hagkvæmasta reikniritið (e. algorithm), eða aðferðin, til að leysa tiltekið verkefni. Um reiknirit, sem einnig kallast algrím, má lesa í svari Snorra Agnarssonar við spurningunni Hvað er algrím og hvernig nýtist það í tölvufræði?

Þessir hópar verkefna eru kallaðir flækjustigsflokkar. Einn af þeim er kallaður P og í honum eru öll verkefni sem hægt er að leysa með fjölda aðgerða sem er í stærðarþrepi (stærðargráðu, order of magnitude) margliðu miðað við stærð inntaksins. Til dæmis ef inntakið er strengur af lengd n þá væri verkefni sem leysa má með n2 aðgerðum í flokknum P en verkefni sem þarf 3n aðgerðir væri ekki í P (af því að fallið 3n er ekki margliða í n). Annar hópur er kallaður NP og í honum eru öll verkefni þar sem hægt er að staðfesta uppgefna lausn með fjölda aðgerða sem er af margliðustærðargráðu miðað við stærð inntaksins.

Í P eru vandamál eins og línuleg bestun, að finna stærsta samnefnara og að ákvarða hvort að tala er prímtala eða ekki. Þessi vandamál eru einnig í NP en til viðbótar er talið að þáttun tölu, ferðasölumannsvandamálið, netlitunarvandamálið og mörg fleiri verkefni séu í NP en ekki í P.

Tengsl flækjustigsflokkana P og NP er enn óleyst vandamál. Það er vitað að P er hlutmengi í NP því ein leið til að staðfesta hvort að tiltekin lausn á verkefni sé rétt er einfaldlega að leysa verkefnið aftur og fá sömu lausn. En það er ekki vitað hvort P og NP séu í raun sama mengið eða sami hópur verkefna. Til einföldunar má segja að spurningin sem þurfi að svara sé ,,er til verkefni þar sem tiltölulega auðvelt er að staðfesta að uppgefin svör séu rétt en mjög erfitt er að finna rétt svör?'' þar sem ,,mjög erfitt" þýðir að hraðvirk tölva gæti verið milljónir ára að leita að réttri lausn með besta reikniritinu sem til væri, en án árangurs. Innifalið í spurningunni er að sýna þarf fram á að ekkert betra reiknirit gæti verið til, það er að segja að vandamálið við að finna lausn á hagkvæman hátt sé ekki skortur á hugmyndaflugi við að uppgötva gott reiknirit heldur sú staðreynd að slíkt hagkvæmt reiknirit sé alls ekki til.

Þessi spurning, ,,er P = NP?'', er ein sú mikilvægasta í tölvunarfræði og hefur til dæmis Clay Mathematics stofnunin boðið eina milljón Bandaríkjadala í verðlaun fyrir rétta lausn.

Svarið við þessari spurningu myndi hafa mikil áhrif á tölvunarfræði, sérstaklega ef niðurstaðan væri sú að P og NP sé sama mengið. Einkum hefði það áhrif á dulmálsfræði, en í dulritun eru notuð verkefni sem vitað er að eru í NP en talið er að séu ekki í P (auðvelt að afkóða ef lykill er til staðar en ómögulegt að brjóta upp dulkóðun án lykils). Ef í ljós kæmi að P og NP er sama mengið þá væri þar með hægt að brjóta upp alla þá dulritun sem notuð er í dag, til dæmis í netbankaviðskiptum, án þess að vera með réttan lykil.

Upphaflega spurningin var:

Getið þið skýrt út fyrir mér hvað felst í stærðfræðivandamálinu ,,P vs. NP'' (sem er eitt af þúsaldarvandamálum Clay-stofnunarinnar)?

Frekara lesefni af Vísindavefnum:

Heimildir

...