ikääntynyt P vs. NP-ongelma
joten mikä sitten on P vs. NP-ongelma?
tiedoksi, status quo on, että P≠NP.
P (polynomial time) tarkoitetaan luokan ongelmia, jotka voidaan ratkaista algoritmi, polynomi kertaa. P-luokan ongelmat voivat vaihdella mistä tahansa niin yksinkertaisesta kuin kertolaskusta listan suurimman luvun löytämiseen. Ne ovat suhteellisen ”helpompi” ongelmakokonaisuus.
VL (ei-deterministinen polynomial time) tarkoitetaan luokan ongelmia, jotka voidaan ratkaista polynomial time ei-deterministinen tietokone., Tämä on olennaisesti toinen tapa sanoa, ”Jos minulla on rajoittamaton laskentatehoa (eli niin monta tietokonetta kuin minä tarvitsen) olen kykenevä ratkaisemaan ongelmia korkeintaan polynomial time”. Enemmän intuitiivisesti, vaikka se viittaa luokan ongelmia, että tällä hetkellä ei ole tapa löytää nopeasti (polynomial time) tarpeeksi vastausta, MUTTA voidaan nopeasti todentaa (polynomial time), jos se tarjoaa ratkaisun ongelmaan. Tässä tarkastettu termi tarkoittaa sitä, että voidaan tarkistaa, että toimitettu ratkaisu on todellakin oikea.
selvästi edellä olevan määritelmän perusteella P ⊆ NP., Katsotaanpa esimerkki havainnollistaa tätä abstrakti ongelma.
yksi yleisimmistä mutta tehokkaimmista esimerkeistä on Sudoku. Kun otetaan huomioon ratkaisematon Sudoku grid (9 x 9 esimerkiksi), se veisi algoritmin melko paljon aikaa ratkaista yksi. Kuitenkin, jos 9 x 9 ruudukko kasvaa 100 x 100 tai 10 000 x 10 000 verkkoon, aika se olisi otettava ratkaista se kasvaa eksponentiaalisesti, koska itse ongelma tulee huomattavasti vaikeampaa., Koska kuitenkin ratkaista Sudoku grid (9 x 9), se on melko helppo tarkistaa, että tietty ratkaisu on todellakin oikea, vaikka koko asteikot 10 000 10 000 hengellä. Se olisi hitaampaa, mutta aika tarkistaa ratkaisu kasvaa hitaammin (polynomisesti).
On olemassa monia muita NP ongelmia siellä, mukaan lukien Selkäreppu ongelma ja myyntiedustajat ongelma, ja ne ovat samanlaisia, että niitä on vaikea ratkaista, mutta nopea tarkistaa., Perustavanlaatuinen ongelma yritämme ratkaista on:
Ei pysty nopeasti tunnistaa NP oikeat vastaukset tarkoita, että siellä on myös nopea tapa löytää ne?
Jos näin on (eli P=NP), tämä voi suuresti muuttaa, miten me tarkastelemme näitä NP-ongelmia, koska se tarkoittaa, että siellä on nopea tapa ratkaista kaikkia näitä ongelmia, vain, että emme ole voineet selvittää, miten, VIELÄ.
jos tämä ei ole tarpeeksi monimutkaista, maustetaan se.,
näiden NP-ongelmien joukossa on kuningas kaikista ongelmista, joita tutkijat kutsuvat NP-täydellisiksi ongelmiksi. Muodollisesti he ovat joukko ongelmia, joista jokainen muu NP ongelma voidaan pienentää (jota käsitellään jäljempänä), polynomi-aikaa ja joiden ratkaisu voi silti olla todennettu polynomi aikaa. Tämä tarkoittaa, että mikä tahansa NP-ongelma voidaan muuntaa NP-täydelliseksi ongelmaksi.
epävirallisesti ne ovat NP-ongelmien ”vaikeimpia”., Näin ollen, jos jokin NP-Täydellinen ongelma voidaan ratkaista polynomi kertaa, sitten joka NP-Täydellinen ongelma voidaan ratkaista polynomin aikaa, ja jokainen ongelma NP voidaan ratkaista polynomial time (eli P=NP). Kuuluisin esimerkki olisi matkustavien myyjien ongelma.
On myös olemassa joukko ongelmia kutsutaan NP-Kovia ongelmia., Nämä ongelmat ovat vähintään yhtä kovaa kuin NP-ongelmia, mutta ilman ehto, joka vaatii, että se voidaan ratkaista polynomin aikaa. Tämä viittaa siihen, että NP-kovat ongelmat eivät välttämättä kuulu NP-luokkaan. Esimerkkinä olisi shakkilaudan ratkaiseminen-kun otetaan huomioon shakkilaudan tila, on lähes mahdotonta sanoa, onko tietty siirto tietyssä tilassa, on itse asiassa optimaalinen siirto. Muodollisesti, ei ole olemassa polynomi aika algoritmi tarkistaa ratkaisu NP-kova ongelma.,
Jos me laittaa kaksi yhdessä, NP-Täydellinen ongelma tarkoittaa, se on NP-Kova, mutta NP-Kova ongelma EI tarkoita, että se on NP-Täydellinen.
Määritellään NP-Täydellisyys
ongelma L, on NP-Täydellinen, jos:
- L, on NP-Kova
- L kuuluu NP
alla Oleva kaavio (painopiste vasemmalla puolella) pitäisi tehdä asioita selkeämpi.,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
Epävirallisesti, ongelma L1 voidaan vähentää toinen ongelma, L2, jos:
- Mahdolliset esimerkiksi L1 voidaan mallintaa esimerkiksi L2
- ratkaisu jälkimmäinen tarjoaa ratkaisun entinen ja päinvastoin
ymmärtää intuitiivisesti, voidaan ajatella sen sellaisenaan:
Jos L1 on pelkistettävissä L2, L1 on oltava enintään yhtä kovaa kuin L2. Vastaavasti L2: n on oltava vähintään yhtä kova kuin L1.
Matemaattisesti, tämä on merkitty seuraavasti: L1 ≤p L2 (luetaan ”L1 on polynomially pelkistettävissä L2”).,
