NP-fullständig
Wikipedia
NP-fullständiga tal (på engelska NP complete) är en klass av matematiska problem som inte kan lösas med någon känd metod, utan man måste gå igenom alla tänkbara lösningar och jämföra dem, vilket kan ta orimligt lång tid. Hur lång tid det tar beror på problemets omfattning.
De NP-fullständiga talen ingår i klassen NP, vilket innebär att tiden som behövs för att lösa ett problem snabbt växer till årmiljoner när problemets omfattning ökar (vilket presenteras bland annat exemplet med det ökande antalet städer i handelsresandeproblemet). Ett annat välkänt exempel på NP-fullständiga problem är Hamiltons problem. Ingen har hittills funnit något sätt att lösa NP-fullständiga problem med en algoritm (alltså på ett enklare sätt än genom att testa alla tänkbara lösningar), men ingen har heller bevisat att det inte går.
Ett problem är NP-fullständigt om det har egenskapen att om det finns en polynomiell deterministisk algoritm för problemet, så finns en polynomiell deterministisk algoritm för alla problem i NP.
