NP-fullständig
Från Rilpedia
NP-fullständiga tal (på engelska NP complete) är en klass av matematiska problem för vilka effektiva lösningar saknas. Den enda lösningen man funnit på ett godtyckligt NP-fullständigt problem är i princip att gå igenom alla tänkbara lösningar och jämföra dem, vilket är ogörligt för andra än små probleminstanser.
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 i 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.
Bland de NP-fullständiga problemen återfinns många viktiga vardagsproblem (optimeringsproblem) t ex industriell logistikoptimering, schemaläggningsproblem och packningsproblem. För många av dessa svåra problem finns dock lösningar som ger bevisbart goda approximationer, och i praktiken används ofta de i brist på exakta lösningar.
