NP-fullständig
NP-fullständiga problem (på engelska NP complete ibland NPC, 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.[1]
Begrepp redigera
De NP-fullständiga problemen ingår i mängden NP som omfattar de problem som går att lösa med en icke-deterministisk algoritm med en tidsåtgång som är en polynomiell funktion av storleken på indata. Mängden P, en delmängd av NP, innehåller de problem som går att lösa med en deterministisk algoritm inom polynomiell tid. De NP-fullständiga problemen är de problem som inte har bevisats tillhöra P.[2]
Tiden för att hitta en lösning på 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 problemet att hitta en Hamiltoncykel i en graf(en). Man kan omvandla ett NP-fullständigt problem till ett annat genom en algoritm som är polynomiell.
Hamiltonproblemet kan överföras till handelseresandeproblemet genom att sätta avståndet mellan varje par av noder till 1 om de förbundna i grafen och till 2 om de inte är förbundna. Därefter löser man handelseresandeproblemet och om den kortaste rutten för handelseresanden är högst antalet noder i grafen, har man funnit en Hamiltoncykel.[3] Ingen har hittills funnit något sätt att lösa NP-fullständiga problem med en polynomiell algoritm, men ingen har heller bevisat att det inte går (se vidare P=NP?).
Exempel redigera
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.
Bakgrund redigera
Det första problemet som visades vara NP-fullständigt är problemet att hitta värden på variablerna som gör ett Booleskt uttryck sant. Det bevisades av Stephen Cook(en) på ACM:s Symposium on Theory of Computing 1971[4] och blev Cook-Levins sats(en).
Referenser redigera
Noter redigera
Tryckta källor redigera
- Sedgewick, Robert (1988). Algorithms. Addison-Wesley. ISBN 0-201-06673-4
Externa länkar redigera
- Cook, Stephen (1971), ”The complexity of theorem proving procedures”, Proc. STOC 1971, s. 151–158, doi:, Stephen Cooks artikel från 1971