Ero sivun ”NP-täydellisyys” versioiden välillä
[arvioimaton versio] | [arvioimaton versio] |
kielioppi |
|||
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 ovat sitä mieltä, että P≠NP. Tätä ei kuitenkaan ole pystytty todistamaan. 11. elokuuta 2010 Vinay Deolalikar väitti |
NP-täydellisten ongelmien ratkaisemiseen tunnetaan ainoastaan eksponentiaalisen ajan vieviä algoritmeja. Yleisesti asiantuntijat ovat sitä mieltä, että P≠NP. Tätä ei kuitenkaan ole pystytty todistamaan. 11. elokuuta 2010 Vinay Deolalikar väitti todistaneensa, että P≠NP.<ref>http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf</ref> Jos P≠NP, avoin ongelma on 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. |
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 18. huhtikuuta 2016 kello 00.07
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. Yleisesti asiantuntijat ovat sitä mieltä, että P≠NP. Tätä ei kuitenkaan ole pystytty todistamaan. 11. elokuuta 2010 Vinay Deolalikar väitti todistaneensa, että P≠NP.[1] Jos P≠NP, avoin ongelma on 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 syklin tai polun löytäminen graafista, Boolen lausekkeiden toteutuvuusongelma ja graafin väritys.