Ero sivun ”NP-täydellisyys” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
p Botti lisäsi: no:NP-komplett |
Ei muokkausyhteenvetoa |
||
| Rivi 1: | Rivi 1: | ||
[[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. |
[[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. Yleisesti asiantuntijat |
NP-täydellisten ongelmien ratkaisemiseen tunnetaan ainoastaan eksponentiaalisen ajan vieviä algoritmeja. 11.8.2010 Vinay Deolalikar todisti, että [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf P≠NP]. Yleisesti asiantuntijat olivat jo sitä mieltä, että näin on, mutta tätä ei kuitenkaan oltu pystytty aiemmin todistamaan. Avoimeksi ongelmaksi jää 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. |
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. |
||
Versio 12. elokuuta 2010 kello 13.37
Laskettavuusteoriassa NP-täydelliset ongelmat ovat laskennallisesti erittäin vaativia ongelmia. Ne ovat luokan NP (epädeterministisellä Turingin koneella polynomiaalisessa 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. 11.8.2010 Vinay Deolalikar todisti, että P≠NP. Yleisesti asiantuntijat olivat jo sitä mieltä, että näin on, mutta tätä ei kuitenkaan oltu pystytty aiemmin todistamaan. Avoimeksi ongelmaksi jää 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 syklin tai polun löytäminen graafista, Boolen lausekkeiden toteutuvuusongelma ja graafin väritys.