24. Toukokuuta 2000, Clay Mathematics Institute keksi seitsemän matemaattisia ongelmia, joiden ratkaisu tahansa ongelma ansaita US $1 000 000 dollarin palkkion ratkaisija. Tunnetusti nimellä vuosituhannen ongelmat, toistaiseksi vain yksi seitsemästä ongelmasta on ratkaistu tähän mennessä.

Wanna make a million dollar, try solving one from this list. Nämä ovat ne ongelmat, jotka on listattu miljoonan dollarin palkintopalkinnoksi.,

  1. Yang–Mills ja Massa Kuilu
  2. Riemannin Hypoteesi
  3. P vs NP-Ongelma
  4. Navierin–Stokesin Yhtälö
  5. Hodge Arveluihin
  6. Poincarén Otaksuma
  7. Koivu ja Swinnerton-Dyer Arveluihin

Okei, olkaamme realistisia täällä, nämä ongelmat ovat täällä syystä. Arvasit oikein, näitä ongelmia on vaikea ratkaista. In-itse asiassa ne ovat syvällisiä ja todella vaikeaa, ei vain ratkaista niitä, mutta jopa ymmärtää ongelman selvitys. Suurin osa luetelluista ongelmista tarvitsee vankkaa aihetuntemusta ja analyysia jopa kysymyksen ymmärtämiseksi.,

Poincarén konjektuuri on ainoa ongelma, joka ratkeaa näiden seitsemän kysymyksen kesken. Tämä ongelma on topologia verkkotunnuksen, joka käsittelee sitä, miten esineet sopivat yhteen ja niiden muoto avaruudessa. Ongelma liittyi nimenomaan sfääreihin.

Vuonna 1904 ranskalainen matemaatikko Henri Poincaré kysyi jos kolme ulotteinen pallo on ominaista ainutlaatuinen yksinkertaisesti liittää kolme moninaiset. Tämä kysymys, Poincarén konjektuuri, oli erikoistapaus Thurstonin geometrisyyskonjektuurista., Perelman on todiste kertoo, että joka kolmas pakosarja on rakennettu joukko vakio-osia, joilla kullakin on yksi kahdeksan hyvin selvää, geometriat.

Lisätietoja: https://www.claymath.org/millennium-problems

Monimutkaista uhmmm! Keskustellaan hieman enemmän tästä ennen siirtymistä P vs. NP.

Henri Poincaré, totesi ongelma vuonna 1904, joka on hyvin yleisesti todetaan, että, jos sinulla on kohde, jossa ei ole reikiä ja sen koko on melko pieni ja rajallinen niin se on pallo (tai voidaan tehdä pallo). Tämä ei koske vain kolmea ulottuvuutta vaan kaikkia ulottuvuuksia.,

Mutta selvitys ei ole todistettu neljäs ulottuvuus, kunnes Grigori Perelman keksi ratkaisu vuonna 2003, joka perustuu työn, jonka Richard Hamilton.

Jos olet kiinnostunut, tässä on mitä miljoonan dollarin ratkaisu näyttää tältä: https://arxiv.org/abs/math/0211159

Grigori Perelman sai miljoona dollari ja fields-mitali, jotka molemmat hän kieltäytyi.

mitä sanoa? Jotkut meistä haluavat ratkaista ongelmia, vain huvikseen ratkaista se.

onni nauttii prosessista!,

P versus NP on viimeisin ongelma oli lueteltu Vuosituhannen Ongelma-luettelosta. Ongelma todettiin vuonna 1971.

tarkka selvitys P vs. NP ongelma otettiin käyttöön vuonna 1971 Stephen Cook hänen uraauurtava kirja ”monimutkaisuus lause osoittautumassa menettelyjä”.

jotta P vs. NP-ongelma ymmärrettäisiin oikein, laskennallisen monimutkaisuuden perustietämys on välttämätön. Itse P vs NP on odotetuin ongelma ratkaisu tietojenkäsittelytieteessä., Joten, hyvä ote siitä, miten tämä ongelma vaikuttaa laskentamaisemaan, auttaa meitä sulattamaan tämän ongelman.

Jos olet uusi aihe laskennallisen kompleksisuuden tai monimutkaisuuden yleensä, olen erittäin rohkaista teitä katsoa osaksi minun edellinen tarina ”Mitä on Laskennallinen Monimutkaisuus?”

Useimmat ongelmat laskennallisen tilaa voidaan pienentää päätöksen ongelma. Se tarkoittaa ongelmia, joissa vastaus on joko kyllä tai ei.

joten palataan kysymykseen, Mikä on P? ja mikä on NP?,

Molemmat P ja NP: n voidaan katsoa olevan joukko ongelmia, jotka on ryhmitelty sen perusteella, kuinka vaikeaa on ratkaista ja arvioida ratkaisu. Termi vaikea on tässä yhteydessä erityisen tärkeä, mikä tarkoittaa käytännössä sitä, miten laskennallisesti intensiivinen ongelma on ratkaista ja tarkistaa ratkaisu.

esimerkiksi tarkastellaan kertolaskun ongelmaa. Tämä on suhteellisen helppo ongelma ratkaista. Ei vain, että tämä ongelma on helppo ratkaista, tämä voidaan myös todentaa yhtä helposti vain kertomalla numeroita., Periaatteessa, mikä tahansa ongelma, joka voidaan ratkaista polynomin aikaa ja tulos, joka voidaan todentaa polynomi aika, on alle monimutkaisuus asettaa P.

P ( polynomial time) sisältää kaikki päätöksen ongelmia, jotka voidaan ratkaista deterministinen Turingin kone käyttämällä polynomi määrän laskenta-aika, tai polynomi aikaa.

on tämä toinen joukko ongelmia, jotka voidaan todentaa polynomi aikaa, mutta jotta voidaan ratkaista tämä ongelma, se vie enemmän kuin polynomi aikaa. Otetaan esimerkiksi Sudoku., Koska meillä on ratkaisu mihin tahansa peliin, voimme varmistaa sen helposti. Tämä tarkoittaa, että voimme tehdä todentamisen osa polynomi aika. Mutta palapelin ratkaisemiseksi tarvitsemme lisää aikaa. Myös verkkojen määrän kasvaessa ratkaisun löytämisen monimutkaisuus kasvaa eksponentiaalisesti.

NP (nondeterministic polynomial time) on monimutkaisuus luokan käytetään luokittelemaan päätöksen ongelmia. NP on asetettu päätöksen ongelmia, joihin ongelma tapauksissa, joissa vastaus on ”kyllä”, on todennettavissa olevat todisteet, polynomi kertaa., (vain saa polynomially suuri, ei suurempi)

Mielenkiintoinen asia huomata on, että jokainen ongelma, joka on P, on myös osa NP. Mutta tämä voi olla tai ei ole vise-päinvastoin. Tässä on, jos tutkimus ajattelutapa piki-in. Niin, ratkaisu NP ongelmat ovat hitaita, mutta ne voidaan todentaa nopeasti. Voimmeko parantaa ratkaisun nopeutta?

Lets look into the primality problem. Primaliteettitesti on algoritmi sen määrittämiseksi, onko tuloluku alkuluku.,

luonnollinen numero n, onko n alkuluku?

Tämän ongelman katsottiin olevan ongelma NP osajoukko, kunnes AKS primality testi osoitti, että tämä ongelma on alle P.,

AKS primality testi (tunnetaan myös nimellä Agrawal–Kayal–Saxena primality testi ja cyclotomic AKS-testi) on deterministinen primality-todistaa algoritmin luonut ja julkaissut Manindra Agrawal, Neeraj Kayal ja Nitin Saxena, tietokone tutkijat Indian Institute of Technology Kanpur, 6. elokuuta, 2002, artikkelissa otsikolla ”ALKULUKUJA on P”

Niin, on olemassa mahdollisuus, että kaikki ongelmat NP voidaan ratkaista P monimutkaisuus?, Tai on olemassa joukko ongelmia, jotka on aina vaikea löytää ratkaisu, jotta P ja NP aina pysyä erillään? Vastausta ei tiedetä. Itse asiassa se on miljoonan dollarin ongelma.

jos on helppo tarkistaa, että ratkaisu ongelmaan on oikea, onko ongelma myös helppo ratkaista?

tyypillinen NP ongelmia on, että Hamiltonin polku ongelma: koska N kaupungeissa vierailla, miten voi tehdä tämän käymättä kaupungissa kahdesti? Jos annat minulle ratkaisun, voin helposti tarkistaa, että se on oikea. Mutta en voi niin helposti löytää ratkaisua.,

Lisätietoja: https://www.claymath.org/millennium-problems/p vs np-ongelma

Joitakin ongelmia NP voidaan ryhmitellä NP-täydellinen. Tämä on ryhmä ongelma, jossa, jos nopea ratkaisu tahansa yksi ongelma on löytynyt, voimme ratkaista ryhmän ongelma samoja monimutkaisuus helposti.

ongelma on NP-täydellinen, kun se voidaan ratkaista rajoitetun luokan brute force haku algoritmeja ja se voidaan simuloida jokin muu ongelma samanlainen algoritmi.,

NP-täydellisyys on erityisen tärkeää, P versus NP keskustelua kuin ratkaisu P-aikaa, sillä ongelma NP-täydellinen osoittaa, että koko monimutkaisuus asettaa romahtaa. Mikä tarkoittaa, että NP-Täydellinen = NP = P

NP-täydellinen ongelma on NP-ja NP-Kova, mikä tarkoittaa, että tämä ongelma on vähintään yhtä kovaa kuin mikä tahansa ongelma NP, kuten on esitetty alla.,

ongelma on NP-kova jos algoritmi ratkaista se voi olla käännetty yksi ratkaisemiseksi tahansa NP-ongelma (nondeterministic polynomial time) ongelma. NP-hard tarkoittaa siis” vähintään yhtä kovaa kuin mikä tahansa NP-ongelma”, vaikka se saattaa itse asiassa olla vaikeampaa.

On olemassa ongelmia ulkopuolella NP, joka on vaikea tehdä ratkaisu samaan aikaan vaikea tarkistaa ratkaisu sekä harkita esimerkiksi shakki., Koska tahansa asennossa aluksella se on vaikea löytää paras seuraava siirto on myös vaikea tarkistaa seuraavan liikkeen olevan oikeita tai ei. Tämä ongelma on EXP (eksponentiaalinen aika monimutkaisuus) ja ehkä ulkopuolella NP.

Useimmat tutkijat alalla laskennallinen monimutkaisuus teoria uskoo, että P ei ole yhtä kuin NP. Tapahtuma vaikka on olemassa monia mielenkiintoisia ongelmia NP, joka vaikuttaa meidän päivä tänään elämä kuin optimointi ongelmia. Ratkaisu NP täydellinen ongelma, kuten proteiinin taitto tarkoittaa, että olemme paljon lähempänä selvittää parannuskeinoa syöpään., Lisäksi, jos P=NP niin saatamme löytää julkisen avaimen salaus on rikki, koska se riippuu kokonaisluku factorisation, joka on ongelma NP ja olemme riippuvaisia tästä, kovuus, liuosta varten useimmat meidän salausta. N=NP: n todistamisen seuraukset ovat siis sekavat.

on tehty paljon tutkimusta joko P = NP tai vise-versa todistamiseksi. Mutta tämä ongelma itsessään näyttää olevan NP-kova (vain olla sarkastinen täällä), koska ei ole ratkaisevia tuloksia kuin nyt. Mutta maailma on paljon mielenkiintoisempi paikka, jos joku voi todistaa, että P=NP., Mutta tällä hetkellä suurin osa alan hyvin koulutetuista ajattelee toisin.

blogissaan, kuuluisa tutkija laskennallinen monimutkaisuus teoria, Scott Aaronson todetaan, että,

Jos P = NP, niin maailma olisi hyvin erilainen paikka kuin me yleensä olettaa sen olevan. Ei olisi mitään erityistä arvoa ”luova harppauksin,” ei perustavanlaatuinen ero ratkaisemaan ongelma ja tunnustaa ratkaisu, kun se on löytynyt., Jokainen, joka voisi arvostaa sinfonia olisi Mozart; jokainen, joka voisi seurata askel-askeleelta argumentti olisi Gauss; jokainen, joka voisi tunnistaa hyvä sijoitusstrategia olisi Warren Buffett.

Kiitos ajastanne.

Edited by Ashok Jeevan