NP-täydellisyys

Laskettavuusteoriassa NP-täydelliset ongelmat ovat laskennallisesti erittäin vaativia ongelmia. Ne ovat luokan NP (epädeterministisellä Turingin koneella polynomisessa 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 polynomisessa ajassa ratkeavat ongelmat ovat myös deterministisellä Turingin koneella polynomisessa 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. 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 polun tai piirin löytäminen verkosta, Boolen lausekkeiden toteutuvuusongelma ja verkon väritys.

Lähteet

Tietojenkäsittelyteoria