NP-fullständig

Från Wikipedia
Hoppa till: navigering, sök

NP-fullständiga problem (på engelska NP complete, från nondeterministic polynomial) ä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 problemen ingår i klassen NP, vilket innebär att tiden som behövs för att verifiera en lösning av problem är en polynomisk funktion av storleken på indata. Tiden för att hitta en lösning för ett NP-fullständigt problem växer dock snabbt 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 polynomisk algoritm, men ingen har heller bevisat att det inte går (se vidare P=NP?).

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.[förtydliga]

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.