Ero sivun ”NP-täydellisyys” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
p r2.7.1) (Botti lisäsi: vi:NP-đầy đủ |
|||
| Rivi 11: | Rivi 11: | ||
[[Luokka:Tietojenkäsittelyteoria]] |
[[Luokka:Tietojenkäsittelyteoria]] |
||
[[ar:مسألة NP كاملة]] |
|||
[[ca:NP-complet]] |
|||
[[cs:NP-úplnost]] |
|||
[[da:NP-komplet]] |
|||
[[de:NP-Vollständigkeit]] |
|||
[[en:NP-complete]] |
|||
[[es:NP-completo]] |
|||
[[fa:انپی کامل]] |
|||
[[fr:Problème NP-complet]] |
|||
[[ko:NP-완전]] |
|||
[[it:NP-Completo]] |
|||
[[nl:NP-volledig]] |
|||
[[ja:NP完全問題]] |
|||
[[no:NP-komplett]] |
|||
[[nn:NP-komplett]] |
|||
[[pl:Problem NP-zupełny]] |
|||
[[pt:NP-completo]] |
|||
[[ru:NP-полная задача]] |
|||
[[simple:NP-complete]] |
|||
[[sk:NP-úplný problém]] |
|||
[[sr:НП-комплетни проблеми]] |
|||
[[sv:NP-fullständig]] |
|||
[[th:เอ็นพีบริบูรณ์]] |
|||
[[vi:NP-đầy đủ]] |
|||
[[uk:NP-повна задача]] |
|||
[[zh:NP完全]] |
|||
Versio 12. maaliskuuta 2013 kello 17.16
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 todistaneen 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.