Metraipolis › archive › dc_5b69d9cc75dc

Problema di funzione — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Problema_di_funzione
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-08T17:18:20.303Z
SHA-256 of the archived text
1a665ddd0bd01374a2763f17526029c5486082df9b5498415b61a0972a2b44d9
Stable URL of this page
https://metraipolis.com/documento/dc_5b69d9cc75dc

How to cite

Problema di funzione — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Problema_di_funzione (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_5b69d9cc75dc (Metraipolis archive dc_5b69d9cc75dc, sha256 1a665ddd0bd01374a2763f17526029c5486082df9b5498415b61a0972a2b44d9)
BibTeX
@misc{dc5b69d9cc75dc,
  title = {Problema di funzione — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Problema_di_funzione},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_5b69d9cc75dc; sha256 1a665ddd0bd01374a2763f17526029c5486082df9b5498415b61a0972a2b44d9},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Problema_di_funzione. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 wi 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)wi+2i. 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à FPNP (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.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «Problema di funzione» — https://it.wikipedia.org/wiki/Problema_di_funzione
Wikidata Q906766: «computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q906766
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Problema_di_funzione?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 82690795, consultata il 2026-11-08T17:14:21.854Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 232799e8df8e307aaa1129adfb429efde41b977c2a3a4d7abbeffe72bc282d6e