Laskennallisen kompleksisuuden teoriassa
NP-taydelliset
ongelmat ovat laskennallisesti erittain vaativia ongelmia. Ne ovat luokan
NP
(epadeterministisella
Turingin koneella
polynomisessa
ajassa ratkeavien ongelmien joukko) vaikeimmat ongelmat. Polynomiaikaisen ratkaisun loytyminen NP-taydelliseen ongelmaan deterministisella Turingin koneella (tai milla tahansa nykyisella tietokoneella) johtaisi polynomiaikaisen ratkaisun olemassaoloon kaikille muillekin luokan NP ongelmille. Tama tarkoittaisi sita, etta
P=NP
, eli kaikki epadeterministisella Turingin koneella polynomisessa ajassa ratkeavat ongelmat ovat myos deterministisella Turingin koneella polynomisessa ajassa ratkeavia.
NP-taydellisten ongelmien ratkaisemiseen tunnetaan ainoastaan eksponentiaalisen ajan vievia algoritmeja. Yleisesti asiantuntijat ovat sita mielta, etta P≠NP. Tata ei kuitenkaan ole pystytty todistamaan. 11. elokuuta 2010 Vinay Deolalikar vaitti todistaneensa, etta P≠NP.
[1]
Jos P≠NP, avoin ongelma on myos, onko luokan NP kaikille ongelmille olemassa jokin ratkaisu, joka vie vahemman kuin eksponentiaalisen ajan.
Tunnettuja NP-taydellisia ongelmia ovat mm.
kauppamatkustajan ongelma
,
Hamiltonin polun
tai piirin loytaminen
verkosta
,
Boolen lausekkeiden
toteutuvuusongelma ja verkon varitys.
