Funktionsproblem - Function problem

I beräkningskomplexitetsteorin är ett funktionsproblem ett beräkningsproblem där en enda utgång (av en total funktion ) förväntas för varje ingång, men utmatningen är mer komplex än den för ett beslutsproblem . För funktionsproblem är utgången inte bara "ja" eller "nej".

Formell definition

Ett funktionellt problem definieras som en relation över strängar i ett godtyckligt alfabet : ${\ displaystyle P}$${\ displaystyle R}$ ${\ displaystyle \ Sigma}$

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

En algoritm löser om algoritmen producerar en sådan för varje ingång så att det finns en tillfredsställande . ${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y) \ i R}$${\ displaystyle y}$

Exempel

Ett välkänt funktionsproblem ges av Functional Boolean Satisfiability Problem, FSAT för kort. Problemet, som är nära besläktat med SAT -beslutsproblemet, kan formuleras enligt följande:

Med tanke på en boolsk formel med variabler , hitta en tilldelning som utvärderar eller beslutar att ingen sådan tilldelning existerar.${\ displaystyle \ varphi}$${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle x_ {i} \ rightarrow \ {{\ text {TRUE}}, {\ text {FALSE}} \}}$${\ displaystyle \ varphi}$${\ displaystyle {\ text {TRUE}}}$

I detta fall ges relationen av tupler av lämpligt kodade booleska formler och tillfredsställande tilldelningar. Medan en SAT -algoritm, matad med en formel , bara behöver returnera "otillfredsställande" eller "tillfredsställande", måste en FSAT -algoritm returnera en tillfredsställande uppgift i det senare fallet. ${\ displaystyle R}$${\ displaystyle \ varphi}$

Andra anmärkningsvärda exempel inkluderar problemet med resande säljare , som ber om rutten som säljaren har tagit, och heltalsfaktoriseringsproblemet , som frågar efter listan över faktorer.

Förhållande till andra komplexitetsklasser

Tänk på ett godtyckligt beslutsproblem i klassen NP . Enligt definitionen av NP har varje probleminstans som svaras "ja" ett certifikat av polynomstorlek som fungerar som ett bevis för "ja" -svaret. Således bildar uppsättningen av dessa tupler en relation, som representerar funktionsproblemet "given in , find a certificate for ". Detta funktionsproblem kallas funktionsvarianten av ; den tillhör klassen FNP . ${\ displaystyle L}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y)}$${\ displaystyle x}$${\ displaystyle L}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle L}$

FNP kan ses som funktionsklass analog NP , i det att lösningar av FNP problem kan vara effektivt (dvs. i polynomisk tid i termer av längden av den ingående) verifierat , men inte nödvändigtvis effektivt hittas . Däremot består klassen FP , som kan betraktas som funktionsklassanalogen av P , av funktionsproblem vars lösningar kan hittas under polynomtid.

Självreducerbarhet

Observera att problemet FSAT som introducerats ovan kan lösas med endast polynomiskt många anrop till en subrutin som avgör SAT -problemet: En algoritm kan först fråga om formeln är tillfredsställande. Därefter kan algoritmen fixa variabeln till TRUE och fråga igen. Om den resulterande formeln fortfarande är tillfredsställande håller algoritmen fast på SANT och fortsätter att fixa , annars bestämmer den att det måste vara FALSKT och fortsätter. Således FSAT är lösbar i polynomisk tid med hjälp av en orakel beslutar SAT . I allmänhet kallas ett problem i NP självreducerbart om dess funktionsvariant kan lösas på polynomtid med hjälp av ett orakel som avgör det ursprungliga problemet. Varje NP-komplett problem är självreducerbart. Det gissas att heltalsfaktoriseringsproblemet inte är självreducerbart. ${\ displaystyle \ varphi}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {1}}$

Reduktioner och fullständiga problem

Funktionsproblem kan reduceras ungefär som beslutsproblem: Med tanke på funktionsproblem och vi säger att det minskar till om det finns beräkningsbara polynomtidsfunktioner och så att det för alla fall av och möjliga lösningar av det gäller att ${\ displaystyle \ Pi _ {R}}$${\displaystyle \Pi _{S}}$${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ Pi _ {S}}$${\ displaystyle f}$${\ displaystyle g}$${\ displaystyle x}$${\ displaystyle R}$${\ displaystyle y}$${\ displaystyle S}$

• Om 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är (x, g (x, y)) \ i R.}$

Det är därför möjligt att definiera FNP-kompletta problem som är analoga med NP-kompletta problem:

Ett problem är FNP-komplett om alla problem i FNP kan reduceras till . Komplexitetsklassen för FNP-kompletta problem betecknas med FNP-C eller FNPC . Därför är problemet FSAT också ett FNP-komplett problem, och det gäller att om och bara om . ${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ mathbf {P} = \ mathbf {NP}}$${\ displaystyle \ mathbf {FP} = \ mathbf {FNP}}$

Totala funktionsproblem

Relationen som används för att definiera funktionsproblem har nackdelen att vara ofullständig: Inte varje ingång har en motsvarighet så . Därför separeras inte frågan om bevisbarhet av bevis från frågan om deras existens. För att övervinna detta problem är det bekvämt att överväga begränsningen av funktionsproblem till totala relationer som ger klassen TFNP som en underklass av FNP . Denna klass innehåller problem som beräkning av ren Nash -jämvikt i vissa strategiska spel där det garanterat finns en lösning. Dessutom, om TFNP innehåller något FNP-komplett problem följer det . ${\ displaystyle R (x, y)}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y) \ i R}$${\ displaystyle \ mathbf {NP} = {\ textbf {co-NP}}}$

Se även

• Beslutsproblem
• Sökproblem
• Räknar problem (komplexitet)
• Optimeringsproblem

Referenser