Problema di funzione
# Problema di funzione

Nella teoria della complessità computazionale, un problema di funzione è un problema computazionale dove ci si aspetta una singola uscita (di una funzione totale) per ogni entrata, ma l'uscita è più complessa di quello di un problema di decisione, cioè, non è solo "SÌ" o "NO". Esempi notevoli includono il problema del commesso viaggiatore, che richiede la strada presa dal commesso viaggiatore, e il problema della fattorizzazione degli interi, che richiede la lista dei fattori.

I problemi di funzione sono più complicati da studiare dei problemi di decisione perché non hanno un analogo ovvio in termini di linguaggi, e perché la nozione di riduzione tra problemi è più sottile in quanto si deve trasformare l'uscita così come l'entrata. I problemi di funzione possono essere ordinati in classi di complessità allo stesso modo dei problemi di decisione. Ad esempio FP è l'insieme dei problemi di funzione che possono essere risolti da una macchina di Turing deterministica in tempo polinomiale, ed FNP è l'insieme dei problemi di funzione che possono essere risolti da una macchina di Turing non deterministica in tempo polinomiale.

Per tutti i problemi di funzione per i quali la soluzione è polinomialmente limitata, c'è un problema decisionale analogo tale che il problema di funzione può essere risolto mediante riduzione di Turing in tempo polinomiale a quel problema decisionale. Per esempio, il problema decisionale analogo al problema del commesso viaggiatore è questo:

    Dato un grafo diretto ponderato e un intero K, c'è un cammino hamiltoniano (o ciclo hamiltoniano se il commesso deve ritornare a casa) con un peso totale minore di o uguale a K?

Data una soluzione a questo problema, possiamo risolvere il problema del commesso viaggiatore come segue. Sia $n$ il numero degli spigoli e sia $w_{i}$ il peso dello spigolo $i$. Per prima cosa riproporzioniamo e perturbiamo i pesi degli spigoli assegnando allo spigolo $i$ il nuovo peso $w'_{i}=2^{(n+1)}w_{i}+2^{i}$. Questo non cambia il cammino hamiltoniano più breve, ma assicura che esso sia unico. Ora si aggiungano i pesi di tutti gli spigoli per ottenere un peso totale $M$. Si trovi il peso del più breve cammino hamiltoniano mediante ricerca binaria: c'è un cammino hamiltoniano con peso $<M/2$; c'è un cammino con peso $<M/4$ ecc. Poi, avendo trovato il peso $W$ del più breve cammino hamiltoniamo, si determini quali spigoli sono nel cammino chiedendo per ciascuno spigolo $i$ se c'è un cammino hamiltoniano con peso $W$ per il grafo modificato, così che lo spigolo $i$ abbia peso $W+1$ (se non c'è tale cammino nel grafo modificato, allora lo spigolo $i$ deve essere nel cammino più breve per il grafo originale).

Questo pone il problema del commesso viaggiatore nella classe di complessità $FP^{NP}$ (la classe dei problemi di funzione che possono essere risolti in tempo polinomiale su una macchina di Turing deterministica con un oracolo per un problema in NP), e infatti esso è completo per quella classe.

