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.
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.
- 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.
Autoritetsdata
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
