Tarkistaminen on helpompaa kuin löytää?
ratkaisun löytämisen ongelmaan pitäisi olla vaikeampaa kuin sen tarkistaminen, että ratkaisu on oikea. Se tuntuu ilmeiseltä, jos olet joskus ratkaissut sudoku palapelin, tai ratkaissut Rubikin kuution, tai pelannut shakkia. Mutta, että lausunto on kuitenkin intuitiivinen näköinen, johtaa meidät suoraan yksi syvimmistä matemaattisia kysymyksiin sivilisaatiomme.
ei-deterministiset polynomiajan (tai NP) ongelmat ovat sellaisia, joissa vastauksen voi helposti tarkistaa oikeaksi., Sen sijaan polynomiajan (tai P) ongelmat ovat niitä
, joissa vastauksen löytäminen on helppoa. Jos voit löytää vastauksen, niin olet tarkistanut sen olevan oikea, joten jokainen ongelma P on myös NP. Sanotaan, että P on NP: n alaluokka. Kuitenkin, emme tiedä, onko ongelma erityisesti NP, joka ei ole P, ja että on mitä me kutsumme P vs NP-ongelma.
P vs NP-ongelma on yksi keskeisimmistä ratkaisemattomista ongelmista matematiikassa ja teoreettisessa tietojenkäsittelytieteessä. On jopa Clay Millennium-palkinto, joka tarjoaa miljoona dollaria sen ratkaisusta., Kuitenkin, on todennäköisesti paljon helpompaa tapoja tulla miljonääri kuin ratkaista P vs NP!
Siellä oli buzz äskettäin, kun joku väitetty ratkaista se arXiv, vaikka aukko todiste oli nopeasti löydetty. Kun otetaan huomioon viimeaikainen kiinnostus ongelmaan ja sen keskeinen paikka matematiikassa, käsittelen sitä tämän viikon blogissa.
Sudoku
Jos saat sanomalehteen täytetyn Sudoku-palapelin, voit heittää sen roskakoriin. Mutta jos haluat, voit selata rivejä, sarakkeita, ja 3 x 3-solut kertoa, että se on kelvollinen ratkaisu: jokainen 1, 2, … , 9 esiintyä tasan kerran., Tämä vastaa NP: tä, sillä on suhteellisen helppo tarkistaa, onko ratkaisu oikea.
kuitenkin, jos annan sinulle osittain täytetyn Sudokupalapelin, ratkaisun löytäminen voi olla vaikeaa. Se on tällaisen palapelin ilo ja haaste. NP: ssä oleminen ei siis heti tunnu vihjaavan, että ongelma on helppo löytää ratkaisu. Että intuitio on ytimessä P vs NP-ongelma.
Tarkka muotoilu
ymmärtää, P ja NP tarkemmin, meidän täytyy paremmin ymmärtää algoritmeja ja mitata niiden nopeuden. Ongelmia aiheuttaa jokin kiinteä panos ja tuotos joko kyllä tai ei. Tulo on tietty pituus, sanotaan n, jossa n on positiivinen kokonaisluku. Tämä edustaa bittien määrää, jonka syötteen ilmaiseminen vaatii. Algoritmi on menetelmä tai menettely ongelman ratkaisemiseksi. Algoritmit antavat ohjeita laskennan jokaisessa vaiheessa ja niiden on loputtava., Vaiheet voivat olla sekunteja, millisekunteja tai jokin muu kiinteä aikaväli, joka riippuu ongelmasta.
monimutkaisuus ongelma on vähintään pahimmassa tapauksessa käyntiaika yli kaikkia mahdollisia algoritmeja ongelman ratkaisemiseksi funktiona pituuden tulo. Toisin sanoen se mittaa, kuinka kauan ongelman ratkaiseminen kestää nopeimmalla algoritmilla, mutta pahimmassa tapauksessa syötöllä.
ongelma on ratkaistavissa polynomiajalla, jos sille annetaan pituuden n tulo, sen monimutkaisuus rajoittuu edellä polynomifunktioon nm jonkin Ei-negatiivisen kokonaisluvun m kohdalla., Joukko kaikki ongelmat ratkaistavissa, polynomi-aika on merkitty P.
koska P ei välttämättä tarkoita, että ongelma on mahdollista. Esimerkiksi, jos se kestää n1000 vaiheet ajaa algoritmi, niin se on toivottoman hidas, vaikka pieni n. Ei-deterministinen polynomi (tai NP) ongelmat ovat sellaisia, jossa voit tarkistaa, jos KYLLÄ-vastaus on oikea, polynomi kertaa.
NP-kovuus
ongelma on NP–kova, jos polynomi-aikainen algoritmi, sillä se merkitsisi sitä, polynomi-algoritmi jokaiseen ongelmaan NP. Näin ollen, jos NP-kova ongelma oli P, niin P = NP., NP-kovat ongelmat ovat vähintään yhtä kovat kuin mikä tahansa NP-ongelma. NP–täydellinen ongelma on yksi, joka on NP-kova ja NP.
klassinen NP-täydellinen ongelma on löytää Hamiltonin sykli. Tätä varten oletetaan, että meillä on kaupunkien verkosto, jota yhdistävät tiet. Ongelmana on vierailla jokaisessa kaupungissa teiden (ei lentokoneita sallittu!) ja palaa alkuun. Tämä tuntuu helpolta pienelle joukolle kaupunkeja, mutta jos niitä olisi annettu satoja, niin siitä tulee vaikeaa., Tuhansia muita tällaisia NP-täydellisiä ongelmia tunnetaan graafiteoriasta, lukuteoriasta, geometriasta ja muista matematiikan ja tietojenkäsittelytieteen aloista.
mikä on vastaus, oikeasti?
Jos veikkaisin, niin olettaisin, että P ei ole NP, ja uskon, että useimmat asiantuntijat olisivat samaa mieltä. Meidän täytyy olla todella tyhmä, ei nähdä kuinka kaikki tuhannet NP-täydellisiä ongelmia ei ole polynomi algoritmi. Mutta lajina tyhmä on oletusasemamme, joten kukaan ei voi sanoa, mikä vastaus on 100% varmuudella.,
Mikä on kiinnostavaa P vs NP-ongelma on, että se osoittaa, kuinka rajallinen ymmärryksemme on todistaa, että tiettyjä ongelmia ei ole nopeita ratkaisuja. Tämä on osa suurempaa laskennallisen kompleksisuusteorian teemaa, joka tutkii kymmeniä muita kompleksisuusluokkia. Tutustu monimutkaisuus eläintarha luettelo näistä luokista. Suurimmaksi osaksi, se on avoin näyttää erilaisia (usein eksoottisia kuulostava) monimutkaisuus luokat ovat asianmukaisia alaluokkia toistensa. Ei esimerkiksi tiedetä, onko NL oikea P: n alaluokka, emmekä tiedä, onko FPT oikea W: n alaluokka.,
todenperäisyydestään huolimatta P vs NP-ongelma pysynee auki vielä jonkin aikaa. Ellei ole todistettu, että P = NP, Sudoku pysyy turvallisena.
Anthony Bonato