Fullstendig (kompleksitet) - Complete (complexity)
I Kompleksitetsteori , en beregnings problem er komplett for en kompleksitet klasse hvis det er, i teknisk forstand, blant de "vanskeligste" (eller "mest uttrykksfulle") problemer i kompleksitet klassen.
Mer formelt kalles et problem p vanskelig for en kompleksitetsklasse C under en gitt type reduksjon hvis det eksisterer en reduksjon (av den gitte typen) fra et problem i C til s . Hvis et problem er både vanskelig for klassen og et medlem av klassen, er det komplett for den klassen (for den typen reduksjon).
Et problem som er komplett for en klasse C sies å være C-komplett , og klassen av alle problemene som er fullført for C er betegnet C-komplett . Den første komplette klassen som ble definert og den mest kjente er NP-complete , en klasse som inneholder mange vanskelige å løse problemer som oppstår i praksis. På samme måte kalles et problem som er hardt for en klasse C, C-hardt , f.eks. NP-hardt .
Normalt antas det at den aktuelle reduksjonen ikke har høyere beregningskompleksitet enn selve klassen. Derfor kan det sies at hvis et C-komplett problem har en "beregningsmessig enkel" løsning, så har alle problemene i "C" en "enkel" løsning.
Vanligvis har kompleksitetsklasser som har en rekursiv oppregning kjente komplette problemer, mens klasser som mangler en rekursiv oppregning ikke har noen. For eksempel har NP , co-NP , PLS , PPA alle kjente naturlige komplette problemer, mens RP , ZPP , BPP og TFNP ikke har noen kjente komplette problemer (selv om et slikt problem kan oppdages i fremtiden).
Det er klasser uten komplette problemer. For eksempel viste Sipser at det er et språk M slik at BPP M ( BPP med oracle M ) ikke har komplette problemer.
