Problema di funzione - Function problem

Nella teoria della complessità computazionale , un problema di funzione è un problema computazionale in cui è previsto un singolo output (di una funzione totale ) per ogni input, ma l'output è più complesso di quello di un problema decisionale . Per problemi di funzione, l'output non è semplicemente "sì" o "no".

Definizione formale

Un problema funzionale è definito come una relazione su stringhe di un alfabeto arbitrario : ${\displaystyle P}$${\displaystyle R}$ ${\displaystyle\Sigma}$

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

Un algoritmo risolve se per ogni input tale che esiste un soddisfacimento , l'algoritmo ne produce uno . ${\displaystyle P}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x,y)\in R}$${\displaystyle y}$

Esempi

Un noto problema di funzione è dato dal Functional Boolean Satisfiability Problem, in breve FSAT . Il problema, che è strettamente correlato al problema decisionale SAT , può essere formulato come segue:

Data una formula booleana con variabili , trova un'assegnazione tale che valuti o decidi che tale assegnazione non esiste.${\displaystyle \varphi}$${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle x_{i}\rightarrow \{{\text{VERO}},{\text{FALSO}}\}}$${\displaystyle \varphi}$${\displaystyle {\text{VERO}}}$

In questo caso la relazione è data da tuple di formule booleane opportunamente codificate e assegnazioni soddisfacenti. Mentre un algoritmo SAT, alimentato con una formula , deve solo restituire "insoddisfacente" o "soddisfacente", un algoritmo FSAT deve restituire qualche assegnazione soddisfacente in quest'ultimo caso. ${\displaystyle R}$${\displaystyle \varphi}$

Altri esempi degni di nota includono il problema del commesso viaggiatore , che richiede il percorso seguito dal venditore, e il problema della fattorizzazione degli interi , che richiede l'elenco dei fattori.

Relazione con altre classi di complessità

Consideriamo un problema di decisione arbitraria nella classe NP . Per definizione di NP , ogni istanza del problema a cui viene risposto "sì" ha un certificato di dimensione polinomiale che funge da prova per la risposta "sì". Quindi, l'insieme di queste tuple forma una relazione, che rappresenta il problema della funzione "dato in , trova un certificato per ". Questo problema di funzione è chiamato variante di funzione di ; appartiene alla classe FNP . ${\displaystyle L}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x,y)}$${\displaystyle x}$${\displaystyle L}$${\displaystyle y}$${\displaystyle x}$${\displaystyle L}$

FNP può essere pensato come l'analogo classe funzione di NP , in quanto le soluzioni di FNP problemi può essere efficace (ossia, in tempo polinomiale in termini di lunghezza dell'input) verificata , ma non necessariamente in modo efficiente trovato . Al contrario, la classe FP , che può essere pensata come l'analogo della classe di funzioni di P , consiste in problemi di funzioni le cui soluzioni possono essere trovate in tempo polinomiale.

Autoriducibilità

Si osservi che il problema FSAT introdotto sopra può essere risolto utilizzando solo polinomialmente molte chiamate a una subroutine che decide il problema SAT : Un algoritmo può prima chiedere se la formula è soddisfacibile. Dopodiché l'algoritmo può fissare la variabile su TRUE e chiedere di nuovo. Se la formula risultante è ancora soddisfacibile l'algoritmo rimane fisso su TRUE e continua a fissare , altrimenti decide che deve essere FALSE e continua. Quindi, FSAT è risolvibile in tempo polinomiale usando un oracolo che decide SAT . In generale, un problema in NP si dice autoriducibile se la sua variante di funzione può essere risolta in tempo polinomiale usando un oracolo che decide il problema originale. Ogni problema NP-completo è auto-riducibile. Si ipotizza che il problema della fattorizzazione degli interi non sia auto-riducibile. ${\displaystyle \varphi}$${\displaystyle x_{1}}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle x_{1}}$

Riduzioni e problemi completi

Problemi di funzione possono essere ridotti tanto come problemi di decisione: dato problemi di funzionalità e diciamo che riduce a se esiste polinomialmente tempo funzioni calcolabili e tale che per tutte le istanze di e le possibili soluzioni di , esso sostiene che ${\displaystyle \Pi _{R}}$${\displaystyle \Pi _{S}}$${\displaystyle \Pi _{R}}$${\displaystyle \Pi _{S}}$${\displaystyle f}$${\displaystyle g}$${\displaystyle x}$${\displaystyle R}$${\displaystyle y}$${\displaystyle S}$

• Se ha una -soluzione, allora ha una -soluzione.${\displaystyle x}$${\displaystyle R}$${\displaystyle f(x)}$${\displaystyle S}$
• ${\displaystyle (f(x),y)\in S\implies (x,g(x,y))\in R.}$

È quindi possibile definire problemi FNP-completi analoghi al problema NP-completo:

Un problema è FNP-completo se ogni problema in FNP può essere ridotto a . La classe di complessità dei problemi FNP-completi è indicata da FNP-C o FNPC . Quindi il problema FSAT è anche un problema FNP-completo , e vale se e solo se . ${\displaystyle \Pi _{R}}$${\displaystyle \Pi _{R}}$${\displaystyle \mathbf {P} =\mathbf {NP}}$${\displaystyle \mathbf {FP} =\mathbf {FNP}}$

Problemi di funzione totale

La relazione utilizzata per definire i problemi di funzione ha lo svantaggio di essere incompleta: non tutti gli input hanno una controparte tale che . Quindi la questione della computabilità delle prove non è separata dalla questione della loro esistenza. Per ovviare a questo problema è conveniente considerare la restrizione dei problemi di funzione alle relazioni totali ottenendo la classe TFNP come una sottoclasse di FNP . Questa classe contiene problemi come il calcolo degli equilibri di Nash puri in alcuni giochi strategici in cui è garantita l'esistenza di una soluzione. Inoltre, se TFNP contiene un problema FNP-completo ne consegue che . ${\displaystyle R(x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x,y)\in R}$${\ Displaystyle \ mathbf {NP} = {\ textbf {co-NP}}}$

Guarda anche

• Problema decisionale
• Problema di ricerca
• Problema di conteggio (complessità)
• Problema di ottimizzazione

Riferimenti