Ero sivun ”NP-täydellisyys” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
p Botti lisäsi: sr:НП-комплетни проблеми |
ML (keskustelu | muokkaukset) NP-täydelliset ongelmat voi muuttaa toisikseen, joten jos yhden pystyy ratkaisemaan polynomisesti, muutkin voi |
||
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.
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
Tunnettuja NP-täydellisiä ongelmia ovat mm. [[kauppamatkustajan ongelma]], [[Hamiltonin syklin]] tai polun löytäminen [[graafi]]sta, Boolen lausekkeiden toteutuvuusongelma ja graafin väritys.
| |||