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 è l'insieme dei problemi di funzione che possono essere risolti da una macchina di Turing deterministica in tempo polinomiale, ed è 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 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 il numero degli spigoli e sia il peso dello spigolo . Per prima cosa riproporzioniamo e perturbiamo i pesi degli spigoli assegnando allo spigolo il nuovo peso . 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 . Si trovi il peso del più breve cammino hamiltoniano mediante ricerca binaria: c'è un cammino hamiltoniano con peso ; c'è un cammino con peso ecc. Poi, avendo trovato il peso del più breve cammino hamiltoniamo, si determini quali spigoli sono nel cammino chiedendo per ciascuno spigolo se c'è un cammino hamiltoniano con peso per il grafo modificato, così che lo spigolo abbia peso (se non c'è tale cammino nel grafo modificato, allora lo spigolo deve essere nel cammino più breve per il grafo originale). Questo pone il problema del commesso viaggiatore nella classe di complessità FPNP (la classe dei problemi di funzione che possono essere risolti in tempo polinomiale su una macchina di Turing deterministica con un per un problema in NP), e infatti esso è completo per quella classe.