Polynomreduksjon
En polynomreduksjon er et verktøy for teoretisk informatikk , nærmere bestemt for kompleksitetsteori . Det er en spesiell klasse av reduksjoner som er spesielt viktig, spesielt for problemet P = NP .
Definisjon
I rammen av formelle språk for beslutningsproblemer , sier vi at et språk kan reduseres i polynomtid til et språk (betegnet ) hvis det eksisterer en beregningsbar funksjon i polynomtid slik at for alle , hvis og bare hvis . Vi kaller funksjonen til reduksjon funksjon , og et polynom algoritme som beregner kalles reduksjon algoritme .
Forholdet mellom et beslutningsproblem og det tilhørende språket
Koding
Enten et avgjørelsesproblem . Forekomster av dette problemet er abstrakte objekter i den forstand at definisjonen deres er rent matematisk. For å tillate implementering av dette problemet, må de imidlertid være representert i en form som er forståelig av programmet. Her kommer forestillingen om koding . Vi definerer en kodingsfunksjon av et beslutningsproblem som et injeksjonsapplikasjon som assosieres med settet med abstrakte forekomster av et element av . Når en programmerer koder et problem, blir således variablene som representerer forekomsten av problemet oversatt (av kompilatoren når det gjelder statiske språk, av tolken når det gjelder dynamiske språk) til binært språk. Koding er derfor en måte å gå fra et abstrakt problem til et konkret problem. Faktisk, hvis løsningen på et beslutningsproblem abstrakt forekomst er når Forekomsten av konkret problem er . Det er imidlertid et lite problem: det er mulig at elementer av ikke tilsvarer noen forekomst av problemet (det vil si at de ikke har noe fortilfelle ). For enkelhets skyld vil vi anta at en slik kjede er bilde 0.
Forholdet mellom beslutningsproblemer og algoritmene som løser dem
- En algoritme aksepterer en streng hvis algoritmen avsluttes , gitt en inngang
- En algoritme avviser en streng hvis .
- Språket akseptert av en algoritme er sett med strenger akseptert av algoritmen, altså .
- Et språk er besluttet av en algoritme hvis noen litt streng som ikke hører til er avvist av .
Vi kan uformelt definere en kompleksitetsklasse som et sett med språk hvis medlemskap bestemmes av et mål på kompleksiteten til en algoritme som bestemmer om en gitt streng tilhører språket . Dermed kan kompleksitetsklassen defineres som det sett av språk som bestemmes av en polynomial tidsalgoritme.
Nytte
Begrepet reduksjon i polynomtid brukes innen rammen av teorien om kompleksiteten til algoritmer for å tillate klassifisering av problemer. Det gjør det mulig å vise på en formell måte og i en polynomisk tid at et problem er minst like vanskelig som et annet: hvis da ikke er vanskeligere enn , eller sagt på en mer teoretisk måte: og har samme klasse av kompleksitet.
Eksempler på reduksjon
- Dekket til delsett-sum
- Klikk for å 3-SAT
- SAT til 3-SAT
- Delsett-sum til SAT
- 3-SAT for å klikke
- 3-SAT til toppunktdeksel