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

17 merkkiä lisätty ,  13 vuotta sitten
p
ei muokkausyhteenvetoa
p (Botti lisäsi: ca:NP-complet)
p
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 polku|Hamiltonin syklin]] tai polun löytäminen [[graafi]]sta, Boolen lausekkeiden toteutuvuusongelma ja graafin väritys.
 
{{Tynkä/Tietotekniikka}}
129

muokkausta