Tämä artikkeli on alun perin ilmestynyt Emolevy Saksa. Alkuperäisen julkaisunsa jälkeen Motherboard US on päivittänyt sitä uusilla tiedoilla. Mitä parannettavissa syövän, reilua kapitalismia, ja täydellinen peli Super Mario Bros. kaikki on yhteistä? Matemaattisen teorian mukaan ratkaisu mihin tahansa näistä ongelmista antaisi meille mahdollisuuden ratkaista muut nopeasti., Tarvitaan vain parempia algoritmeja, jotka todistavat, että monimutkaiset kysymykset—kuten proteiinien taitto, tehokkaat markkinapaikat ja kombinatoriset analyysit—ovat vain muunnelmia yksinkertaisemmista ongelmista, joita supertietokoneet pystyvät jo ratkaisemaan. Mutta miten yksi algoritmi yksinkertaistaa erittäin monimutkaisia ongelmia? Se riippuu toisesta kysymyksestä: entä jos monimutkaiset ongelmat ovat todellisuudessa vain yksinkertaisia ongelmia valepuvussa?, Tämä arvoitus on edelleen yksi suurimmista ratkaisemattomista kysymyksistä modernin matematiikan, ja on yksi seitsemästä Millennium-Palkinnon Ongelmia, joista jokainen hyväksytty vastaus palkitaan miljoona dollaria.
Nyt, saksalainen mies nimeltä Norbert Blüm on väitti on ratkaista edellä arvoitus, joka on oikein kutsutaan P vs NP-ongelma. Valitettavasti hänen väitetty ratkaisunsa ei ole hyvä uutinen., Bonnin yliopistosta kotoisin oleva Blum väittää vastikään julkaistussa 38-sivuisessa paperissaan, että P ei ole NP: n veroinen. Toisin sanoen, monimutkainen ongelmat ovat pohjimmiltaan erilaisia kuin suoraviivainen ongelmia, ja se ei näytä kuin meidän korkean suorituskyvyn tietokoneita voi murtaa nämä vaikeimmista ongelmista milloin lähitulevaisuudessa. Ja päivinä, koska hänen paperin julkaistiin, lukuisat matemaatikot ovat alkaneet herättää kysymyksiä siitä, onko Blum ratkaistu se ollenkaan.
mikä tarkalleen on P vs. NP-ongelma?,
useimmat tietojenkäsittelytieteilijät ovat yleensä samaa mieltä Blumin päätelmästä. Kovat ongelmat ovat vaikeita, helpot ongelmat helppoja. Computer science, helppo ongelmia, kuuluvat yleensä varjolla P. Tämä tarkoittaa, että ne voidaan ratkaista ”polynomial time”, joka on paljon, kuten sanomalla, että ne voidaan ratkaista kohtuullisessa ajassa. Paljon vaikeampia ovat NP-ongelmat, joita tietokoneet eivät pysty ratkaisemaan kohtuullisessa ajassa. Käytännön tarkoituksiin NP-ongelmat voivat yhtä hyvin olla tietokoneiden ratkaisemattomia., (Huomaa kuitenkin, että NP tulee sanoista ”nondeterministic polynomial time” eikä ”ole polynomi” aikaa.) Tässä muutamia esimerkkejä NP-ongelmista:
proteiinin taitto: prosessi, jonka kautta biologisen organismin proteiinit saavat rakenteensa. Parempi käsitys tästä prosessista voisi auttaa meitä tunnistamaan tai jopa estämään mutaatioita, jotka voivat parantaa tiettyjä syövän muotoja. Optimoitu reititys: optimoitu matkareitti 15 eri kaupungin läpi käymättä samassa kaupungissa kahdesti?, Kova pähkinä purtavaksi, jopa supertietokoneelle, minkä vuoksi tätä pidetään myös tietojenkäsittelytieteen NP-ongelmana.
täydellinen shakkipeli: shakkipeli on ääretön mahdollisia liikkeitä, niin, että jopa supertietokoneen kanssa uskomaton kapasiteettia ei voi määrittää, täydellinen taktiikka. Monet matemaatikot pitävät tätä ongelmaa niin vaikeana, että he eivät pidä sitä NP-ongelmana, vaan pitävät sitä täysin pois mahdollisuuksien valtakunnasta.,
Kaikki nämä monimutkaiset ongelmat ovat yksi yhteinen asia: niin vaikeaa Kuin se voi löytää ratkaisu NP-ongelmia, se on suhteellisen helppo tarkistaa, ovatko ratkaisut, kun sinulla on ne.
Nämä kaksi kategorinen ero, ongelma monimutkaisuus on alkuperä ennen yhteiskunnalliset nousu kotiin tietokoneissa. 1970-luvulla, kun tietokoneet vielä olivat koko kömpelöitä jääkaappi, se oli nopeasti todennut, että ei kaikki ihmiskunnan ongelmat voitaisiin yksinkertaisesti ratkaista ne koneet., Ehdotettiin, että ero voitaisiin virallistaa laskennallisen monimutkaisuuden kannalta, mikä johtaisi kompleksisuusluokkien joukkoon, mukaan lukien N ja NP.
Koska virallista määritelmää, P ja NP vuonna 1971, tietokone tutkijat ovat kiistelleet siitä, onko vai ei se olisi mahdollista keksiä algoritmi, jolla voidaan vähentää tai uudelleen NP ongelmat sellaisia, että ne voidaan ratkaista polynomin aikaa. Jos joku pystyy osoittamaan, että kaikki NP-ongelmat ovat viime kädessä vain P-ongelmien variaatioita, kaikki NP-ongelmat olisivat periaatteessa saman vähennyksen alaisia., Toisin sanoen täydellisen Super Mario Bros.-taktiikan tunteva voi myös parantaa syövän.
yhteensä 116 rohkeimmat niiden kenttä on virallisesti yrittänyt ratkaista tätä mysteeriä (vaikka untold enemmän tietokone tutkijat ovat kirjoittaneet olisi ratkaisuja messageboards ja sivustot, kuten arXiv). Tähän mennessä mikään näistä todisteista ei ole virallisesti tunnustettu matematiikan yhteisössä.
a Sort of Who Wants to be a Millionaire?, Matemaatikot
Vuonna 2000, Clay Mathematics Institute (CMI), joka sijaitsee Oxford, koonneet seitsemän selvittämätöntä Millennium-Palkinnon Ongelmia, sitomista miljoona dollaria jokaisesta ratkaisu. Kuka haluaa miljonääriksi? tai X-palkinto matemaatikoille. Millennium-palkinnon ongelmia pidetään poikkeuksellisen vaikeina asiantuntijapiireissäkin. Kysymyksienkin ymmärtämiseksi tarvitaan runsaasti kenttäkohtaista tietoa., Ainoa Millennium-Palkinnon Ongelma ratkaistu tähän mennessä on Poincarén otaksuma, joka ei ole helposti selitettävissä sivuhuomautuksena artikkelin eri matematiikan käsite.
NP-ongelman ratkaiseminen ei olisi ihan hyvä asia. Esimerkiksi suurin osa salauksesta perustuu siihen, että on vaikea factoroida hyvin suuria alkulukuja. Kokonaisluku factorization on luokan NP ongelma. 256-bittistä koodia, jollaisia rahoituslaitokset käyttävät online-luottokorttimaksuissa, pidetään murtumattomana ja siten erittäin turvallisena., Jos joku todistaa, että NP tekee yhtä P, pankkien olisi nopeasti keksittävä erilainen tietoturvamenetelmä.
mitä mieltä matemaatikot ovat Blumin matemaattisesta todistuksesta?
Koska Blumin kirja julkaistiin, matemaatikot ja tietotekniikan tutkijoita ympäri maailmaa ovat raastava niiden aivot, onko Bonn-perustuu tutkijan on itse asiassa ratkaista tämä Millennium-Palkinnon Ongelma. Alun perin positiivisen reaktion, kuten Stanfordin matemaatikon Reza Zadehin, jälkeen alkaa herätä epäilyksiä siitä, onko Blumin päättely oikein.,
foorumi teoreettisen matematiikan, käyttäjä nimetty Mihail tavoitti Alexander Razborov—kirjoittanut kirjan, joka Blum on todiste perustuu—kysyä häneltä Blum on paperia. Razborov väittää löytäneensä virheen Blumin paperista: Blumin pääargumentti on ristiriidassa yhden Razborovin keskeisistä oletuksista kanssa. Ja matemaatikko Scott Aaronson, joka on jotain viranomaisen matematiikan yhteisöä, kun se tulee P vs., NP: n mukaan hän olisi valmis lyömään 200 000 dollaria vetoa, ettei Blumin matemaattinen todiste kestä. ”Älkää kysykö”, Aaronson kirjoittaa. Jos todisteita ei ole kumottu, ” voit tulla takaisin ja sanoa, että olin umpihullu.”Aaronsonin alkuperäisen blogikirjoituksen jälkeisellä viikolla muut matemaatikot ovat alkaneet yrittää tökkiä reikiä Blumin todisteisiin. Georgia Techin tietojenkäsittelytieteen professori Dick Lipton kirjoitti blogikirjoituksessaan, että Blumin todistus ”läpäisee monia vakavuussuodattimia”, mutta vihjasi, että siinä voi olla joitakin ongelmia., Commenter, että blogi, joka tunnetaan vain nimellä ”vloodin,” totesi, että ”yksi virhe on hienovarainen piste” todiste; muut matemaatikot ovat sittemmin chimed ja vahvisti vloodin on alustava analyysi, ja niin syntymässä yksimielisyys monet matemaatikot on, että ratkaista P vs. NP edelleen heikko. Suomentanut Melina McCormack.