Ero sivun ”NP-täydellisyys” versioiden välillä

NP-täydellisyys (muokkaa)

Versio 13. elokuuta 2010 kello 11.24

14 merkkiä lisätty ,  10 vuotta sitten
Neutraalimmaksi, Deolalikarin todiste ei ole vielä käynyt läpi peer-reviewtä?
(Neutraalimmaksi, Deolalikarin todiste ei ole vielä käynyt läpi peer-reviewtä?)
[[Laskettavuus]]teoriassa '''NP-täydelliset''' ongelmat ovat laskennallisesti erittäin vaativia ongelmia. Ne ovat luokan NP (epädeterministisellä [[Turingin kone]]ella [[polynomi]]aalisessa ajassa ratkeavien ongelmien joukko) vaikeimmat ongelmat. Polynomiaikaisen ratkaisun löytyminen NP-täydelliseen ongelmaan deterministisellä Turingin koneella (tai millä tahansa nykyisellä tietokoneella) johtaisi polynomiaikaisen ratkaisun olemassaoloon kaikille muillekin luokan NP ongelmille. Tämä tarkoittaisi sitä, että [[P=NP]], eli kaikki epädeterministisellä Turingin koneella polynomiaalisessa ajassa ratkeavat ongelmat ovat myös deterministisellä Turingin koneella polynomiaalisessa ajassa ratkeavia.
 
NP-täydellisten ongelmien ratkaisemiseen tunnetaan ainoastaan eksponentiaalisen ajan vieviä algoritmeja. 11Yleisesti asiantuntijat ovat sitä mieltä, että P≠NP.8 Tätä ei kuitenkaan ole pystytty todistamaan. 11. elokuuta 2010 Vinay Deolalikar todisti,väitti todistaneen että [P≠NP.<ref>http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf</ref> P≠NP]. Yleisesti asiantuntijat olivat joJos sitä mieltäP≠NP, ettäavoin näinongelma on, mutta tätä ei kuitenkaan oltu pystytty aiemmin todistamaan. Avoimeksi ongelmaksi jäämyös, onko luokan NP kaikille ongelmille olemassa jokin ratkaisu joka vie vähemmän kuin eksponentiaalisen ajan.
 
Tunnettuja NP-täydellisiä ongelmia ovat mm. [[kauppamatkustajan ongelma]], [[Hamiltonin polku|Hamiltonin syklin]] tai polun löytäminen [[graafi]]sta, Boolen lausekkeiden toteutuvuusongelma ja graafin väritys.
Jniemenmaa
seulojat
20 299

muokkausta

Noudettu kohteesta ”https://fi.wikipedia.org/wiki/Toiminnot:MobileDiff/8894652”