Funksjonsproblem - Function problem

I beregningskompleksitetsteori er et funksjonsproblem et beregningsproblem der det forventes en enkelt utgang (av en total funksjon ) for hver inngang, men utgangen er mer kompleks enn for et beslutningsproblem . For funksjonsproblemer er utgangen ikke bare "ja" eller "nei".

Formell definisjon

Et funksjonelt problem er definert som en relasjon over strenger i et vilkårlig alfabet : ${\ displaystyle P}$${\ displaystyle R}$ ${\ displaystyle \ Sigma}$

${\ displaystyle R \ subseteq \ Sigma ^{*} \ times \ Sigma ^{*}}$

En algoritme løser hvis algoritmen produserer en slik for hver inngang slik at det finnes en tilfredsstillende . ${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y) \ i R}$${\ displaystyle y}$

Eksempler

Et velkjent funksjonsproblem er gitt av Functional Boolean Satisfiability Problem, FSAT for kort. Problemet, som er nært knyttet til SAT -avgjørelsesproblemet, kan formuleres som følger:

Gitt en boolsk formel med variabler , finn en oppgave som evaluerer til eller avgjør at ingen slik tildeling eksisterer.${\ displaystyle \ varphi}$${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle x_ {i} \ rightarrow \ {{\ text {TRUE}}, {\ text {FALSE}} \}}$${\ displaystyle \ varphi}$${\ displaystyle {\ text {TRUE}}}$

I dette tilfellet er relasjonen gitt av tupler av passende kodede boolske formler og tilfredsstillende oppgaver. Mens en SAT -algoritme, matet med en formel , bare trenger å returnere "utilfredsstillende" eller "tilfredsstillende", må en FSAT -algoritme returnere en tilfredsstillende oppgave i sistnevnte tilfelle. ${\ displaystyle R}$${\ displaystyle \ varphi}$

Andre bemerkelsesverdige eksempler inkluderer problemet med omreisende selger , som ber om ruten som selgeren har tatt, og heltallsfaktoriseringsproblemet , som ber om listen over faktorer.

Forholdet til andre kompleksitetsklasser

Vurder et vilkårlig beslutningsproblem i klasse NP . Ved definisjonen av NP har hver problemforekomst som blir svart "ja" et polynomstørrelsessertifikat som fungerer som et bevis for "ja" -svaret. Dermed danner settet med disse tuplene en relasjon, som representerer funksjonsproblemet "gitt inn , finn et sertifikat for ". Dette funksjonsproblemet kalles funksjonsvarianten av ; den tilhører klassen FNP . ${\ displaystyle L}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y)}$${\ displaystyle x}$${\ displaystyle L}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle L}$

FNP kan betraktes som funksjonsklassenes analoge av NP , ved at løsninger på FNP -problemer effektivt kan verifiseres (dvs. i polynomtid når det gjelder innspillets lengde) , men ikke nødvendigvis effektivt finnes . I kontrast består klassen FP , som kan betraktes som funksjonsklassenes analoge av P , av funksjonsproblemer hvis løsninger kan bli funnet i polynomtid.

Selvreduserbarhet

Legg merke til at problemet FSAT som ble introdusert ovenfor, kan løses bare ved å bruke polynomisk mange anrop til en subrutine som avgjør SAT -problemet: En algoritme kan først spørre om formelen er tilfredsstillende. Etter det kan algoritmen fikse variabelen til TRUE og spør igjen. Hvis den resulterende formelen fortsatt er tilfredsstillende, holder algoritmen fast på TRUE og fortsetter å fikse , ellers bestemmer den at det må være FALSE og fortsetter. Dermed kan FSAT løses i polynom tid ved bruk av et orakel -avgjørende SAT . Generelt kalles et problem i NP selvreduserende hvis funksjonsvarianten kan løses på polynomstid ved hjelp av et orakel som avgjør det opprinnelige problemet. Hvert NP-komplett problem er selvreduserende. Det antas at heltallfaktoriseringsproblemet ikke er selvreduserende. ${\ displaystyle \ varphi}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {1}}$

Reduksjoner og komplette problemer

Funksjonsproblemer kan reduseres omtrent som beslutningsproblemer: Gitt funksjonsproblemer og vi sier at det reduseres til hvis det eksisterer polynomisk tidsberegnbare funksjoner og slik at det for alle forekomster av og mulige løsninger av , holder at ${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ Pi _ {S}}$${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ Pi _ {S}}$${\ displaystyle f}$${\ displaystyle g}$${\ displaystyle x}$${\ displaystyle R}$${\ displaystyle y}$${\ displaystyle S}$

• Hvis har en -løsning, har den en -løsning.${\ displaystyle x}$${\ displaystyle R}$${\ displaystyle f (x)}$${\ displaystyle S}$
• ${\ displaystyle (f (x), y) \ i S \ innebærer (x, g (x, y)) \ i R.}$

Det er derfor mulig å definere FNP-komplette problemer som er analoge med NP-komplette problemet:

Et problem er FNP-komplett hvis hvert problem i FNP kan reduseres til . Kompleksitetsklassen for FNP-komplette problemer er angitt med FNP-C eller FNPC . Derfor er problemet FSAT også et FNP-komplett problem, og det holder at hvis og bare hvis . ${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ mathbf {P} = \ mathbf {NP}}$${\ displaystyle \ mathbf {FP} = \ mathbf {FNP}}$

Totale funksjonsproblemer

Forholdet som brukes for å definere funksjonsproblemer, har den ulempen at den er ufullstendig: Ikke alle innganger har en motpart slik . Derfor er ikke spørsmålet om bevisbarhet av bevis skilt fra spørsmålet om deres eksistens. For å overvinne dette problemet er det praktisk å vurdere begrensningen av funksjonsproblemer til totale relasjoner som gir klassen TFNP som en underklasse av FNP . Denne klassen inneholder problemer som beregning av ren Nash -likevekt i visse strategiske spill der det garantert finnes en løsning. I tillegg, hvis TFNP inneholder et FNP-komplett problem, følger det det . ${\ displaystyle R (x, y)}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y) \ i R}$${\ displaystyle \ mathbf {NP} = {\ textbf {co-NP}}}$

Se også

• Beslutningsproblem
• Søkeproblem
• Telleproblem (kompleksitet)
• Optimaliseringsproblem

Referanser