Funktionsproblem - Function problem

I beregningskompleksitetsteori er et funktionsproblem et beregningsproblem, hvor der forventes et enkelt output (af en total funktion ) for hvert input, men output er mere komplekst end et beslutningsproblem . For funktionsproblemer er outputtet ikke bare 'ja' eller 'nej'.

Formel definition

Et funktionelt problem er defineret som en relation over strenge i et vilkårligt alfabet : ${\ displaystyle P}$${\ displaystyle R}$ ${\ displaystyle \ Sigma}$

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

En algoritme løser, hvis algoritmen producerer en sådan for hvert input, så der er tilfredsstillende . ${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y) \ i R}$${\ displaystyle y}$

Eksempler

Et velkendt funktionsproblem er givet af Functional Boolean Satisfiability Problem, FSAT for short. Problemet, der er tæt forbundet med SAT -beslutningsproblemet, kan formuleres som følger:

I betragtning af en boolsk formel med variabler skal du finde en opgave , der evaluerer til eller beslutter, at der ikke findes en sådan tildeling.${\ displaystyle \ varphi}$${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle x_ {i} \ rightarrow \ {{\ text {TRUE}}, {\ text {FALSE}} \}}$${\ displaystyle \ varphi}$${\ displaystyle {\ text {TRUE}}}$

I dette tilfælde er relationen givet af tupler af passende kodede boolske formler og tilfredsstillende opgaver. Mens en SAT -algoritme, der er fodret med en formel , kun behøver at returnere "utilfredsstillende" eller "tilfredsstillende", skal en FSAT -algoritme returnere en tilfredsstillende opgave i sidstnævnte tilfælde. ${\ displaystyle R}$${\ displaystyle \ varphi}$

Andre bemærkelsesværdige eksempler omfatter problemet med omrejsende sælger , der beder om ruten, som sælgeren har taget, og heltalsfaktoriseringsproblemet , der beder om listen over faktorer.

Forholdet til andre kompleksitetsklasser

Overvej et vilkårligt beslutningsproblem i klasse NP . Ved definitionen af NP har hver problemforekomst, der bliver svaret 'ja', et certifikat i polynomstørrelse, der tjener som bevis for 'ja'-svaret. Således danner sættet af disse tupler en relation, der repræsenterer funktionsproblemet "givet i , find et certifikat for ". Dette funktionsproblem kaldes funktionsvarianten af ; det 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 betragtes som funktionsklasse -analog af NP , idet løsninger af FNP -problemer effektivt (dvs. i polynomisk tid med hensyn til længden af ​​input) kan verificeres , men ikke nødvendigvis findes effektivt . I modsætning hertil består klassen FP , der kan betragtes som funktionsklasseanalogen af P , af funktionsproblemer, hvis løsninger kan findes i polynomisk tid.

Selvreducerbarhed

Bemærk, at ovenstående problem FSAT kan løses ved hjælp af kun polynomisk mange opkald til en underrutine, der afgør SAT -problemet: En algoritme kan først spørge, om formlen er tilfredsstillende. Derefter kan algoritmen rette variablen til SAND og spørge igen. Hvis den resulterende formel stadig er tilfredsstillende, holder algoritmen fast på SAND og fortsætter med at rette , ellers beslutter den, at det skal være FALSKT og fortsætter. Således kan FSAT løses i polynomisk tid ved hjælp af et orakel, der afgør SAT . Generelt kaldes et problem i NP selvreducerbart, hvis dets funktionsvariant kan løses på polynomisk tid ved hjælp af et orakel, der afgør det oprindelige problem. Hvert NP-komplet problem er selvreducerbart. Det formodes, at heltalsfaktoriseringsproblemet ikke er selvreducerbart. ${\ displaystyle \ varphi}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {1}}$

Reduktioner og komplette problemer

Funktionsproblemer kan reduceres på samme måde som beslutningsproblemer: I betragtning af funktionsproblemer, og vi siger, at det reduceres til, hvis der eksisterer polynomisk tidsberegnelige funktioner og sådan, at det for alle tilfælde af og mulige løsninger af , fastholder, 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 -opløsning, har den en -løsning.${\ displaystyle x}$${\ displaystyle R}$${\ displaystyle f (x)}$${\ displaystyle S}$
• ${\ displaystyle (f (x), y) \ i S \ indebærer (x, g (x, y)) \ i R.}$

Det er derfor muligt at definere FNP-komplette problemer analogt med NP-komplette problem:

Et problem er FNP-komplet, hvis alle problemer i FNP kan reduceres til . Kompleksitetsklassen af FNP-komplette problemer betegnes med FNP-C eller FNPC . Derfor er problemet FSAT også et FNP-komplet problem, og det holder, at hvis og kun hvis . ${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ mathbf {P} = \ mathbf {NP}}$${\ displaystyle \ mathbf {FP} = \ mathbf {FNP}}$

Samlede funktionsproblemer

Den relation, der bruges til at definere funktionsproblemer, har den ulempe, at den er ufuldstændig: Ikke alle input har et modstykke , der gør det . Derfor er spørgsmålet om bevisers beregnelighed ikke adskilt fra spørgsmålet om deres eksistens. For at overvinde dette problem er det praktisk at overveje begrænsningen af ​​funktionsproblemer til totale relationer, der giver klassen TFNP som en underklasse af FNP . Denne klasse indeholder problemer som beregning af ren Nash -ligevægt i visse strategiske spil, hvor der garanteret findes en løsning. Hvis TFNP indeholder et FNP-komplet problem, følger det derudover . ${\ displaystyle R (x, y)}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y) \ i R}$${\ displaystyle \ mathbf {NP} = {\ textbf {co-NP}}}$

Se også

• Beslutningsproblem
• Søgeproblem
• Tælle problem (kompleksitet)
• Optimeringsproblem

Referencer