Kompleksitetsklasse
I kompleksitetsteori er ei kompleksitetsklasse ei mengde problemer med lik ressurbasert kompleksitet. NP, P, og PSPACE er eksempler på slike kompleksitetsklasser.
Ei kompleksitetsklasse har gjerne en definisjon på følgende form.
- Mengda av problemer som kan løses av en abstrakt maskin M med O(f(n)) ressurser hvor n er inputstørrelsa.
I klassene NP og P er det tid som er ressursen, mens det i klasser som PSPACE er snakk om plass.
Reduksjoner
[rediger | rediger kilde]Mange kompleksitetsklasser er definert ved bruk av reduksjoner. En reduksjon av et problem er å transformere problemet til et liknende problem. Uformelt sier man at problemet må være minst like vanskelig som et annet problem. Dette er svært nyttig for å finne ei løsning på ulike problemer. Hvis et problem X kan løses ved bruk av en algoritme for et problem Y, vil X ikke være et hardere problem enn Y og man sier dermed at X kan reduseres til Y. Det finnes mange ulike måter å gjøre reduksjoner på, men en av de mest brukte er polynomielltidsreduksjoner.
Dette betyr at reduksjonen tar polynomiell tid, altså at det å transformere et gitt problem til et annet gjøres i polynomiell tid. Polynomielltidsreduksjoner brukes blant annet om man ønsker å vise at et gitt problem er NP-komplett. For eksempel problemet for å finne verdier som tilfredsstiller en boolsk formel (også kjent som SAT) er polynomielltidsreduserbart til delmengdesumproblemet, altså å finne talla i ei mengde som summerer opp til et gitt tall.
Et problem X kalles hardt for ei kompleksitetsklasse K hvis alle problemer i K kan reduseres til X. Med andre ord finnes det intet problem i K som er hardere enn X. En algoritme for X vil løse alle problemer i K. Reduksjonen det snakkes om fra problemene i K til X vil sjølsagt være avhengig av hvilke kompleksitetsklasser det snakkes om. I kompleksitetsklasser større enn P er det ofte snakk om polynomielltidsreduksjoner. Mengda av disse harde problemene for ei kompleksitetsklasse K får ofte navn. Et eksempel på dette er der de problemene som er hardt for NP. De kalles NP-hardt.
Hvis problemet X attpåtil er med i kompleksitetsklassa K, så kalles problemet komplett. Dette betyr da at X er et av de hardeste problemene i K. Ei mengde av slike harde problemer får ofte et eget navn. Et eksempel er NP-komplette problemer, som er alle de NP-harde problemene som er med i NP. I praksis vil en ofte prøve å redusere et problem til et NP-komplett problem for å vise at problemet ikke er løselig i polynomiell tid. Dette er da under antakelsa om at NP er forskjellig fra P, som fortsatt er et uløst problem kalt P=NP-problemet.
Litteratur
[rediger | rediger kilde]- Michael Garey og David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979.
- Neil Immerman. «Computational Complexity Theory». Arkivert fra originalen 16. april 2016. Arkivert 16. april 2016 hos Wayback Machine.