Ero sivun ”NP-täydellisyys” versioiden välillä
[arvioimaton versio] | [arvioimaton versio] |
p Botti muokkasi: he:מחלקת הסיבוכיות NPC |
p Botti muokkasi: he:NPC (מחלקת סיבוכיות) |
||
Rivi 17: | Rivi 17: | ||
[[ko:NP-완전]] |
[[ko:NP-완전]] |
||
[[it:NP-Completo]] |
[[it:NP-Completo]] |
||
[[he:מחלקת |
[[he:NPC (מחלקת סיבוכיות)]] |
||
[[nl:NP-volledig]] |
[[nl:NP-volledig]] |
||
[[ja:NP完全問題]] |
[[ja:NP完全問題]] |
Versio 24. heinäkuuta 2008 kello 18.21
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. 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.