Wikipedia

Ero sivun ”NP-täydellisyys” versioiden välillä

Selaa historiaa interaktiivisesti
[arvioimaton versio][arvioimaton versio]
← Vanhempi muutosUudempi muutos →
Poistettu sisältö Lisätty sisältö
VisuaalinenWikiteksti
wikitystä, vähän lisää tavaraa
p w
Rivi 1:
[[LaskettavuusteoriaLaskettavuus]]ssateoriassa 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. Jos P≠NP, avoin ongelma on myös, onko luokan NP kaikille ongelmille olemassa jokin ratkaisu joka vie vähemmän kuin eksponentiaalisen ajan.
Noudettu kohteesta ”https://fi.wikipedia.org/wiki/NP-täydellisyys”