title: Problema computazionale
text: # Problema computazionale
  
  Nell'informatica teorica, un problema computazionale o problema astratto è una relazione tra un insieme di istanze e un insieme di soluzioni. Un problema computazionale permette di stabilire formalmente la relazione desiderata tra l'entrata o input di un algoritmo e la sua uscita o output. Una soluzione algoritmica a un problema computazionale consiste in un algoritmo che per ogni istanza del problema calcola almeno una soluzione corrispondente – nel caso esista – o certifica che non esiste alcuna soluzione. Un problema astratto diventa un problema concreto quando le istanze e le soluzioni sono codificate in forma di linguaggi formali.
  
  I problemi computazionali sono soliti essere definiti in due parti: nella prima si descrive l'insieme di istanze e nella seconda si descrive la soluzione attesa per ogni istanza. Per esempio, il problema dell'ordinamento di numeri interi si definisce di solito come segue:
  
      Istanza: Una successione finita di numeri interi $\left(a_{1},a_{2},\ldots ,a_{n}\right)$
      Soluzione: Una permutazione $\left(a_{1}^{\prime },a_{2}^{\prime },\ldots ,a_{n}^{\prime }\right)$ della successione in entrata tale che $a_{1}^{\prime }\leq a_{2}^{\prime }\leq \cdots \leq a_{n}^{\prime }$
  
  Qui tanto l'insieme delle istanze quanto quello delle soluzioni è lo stesso, poiché si tratta dell'insieme di tutte le successioni finite di numeri interi. La relazione che vi è tra di essi assegna a ogni successione $\left(a_{1},a_{2},\ldots ,a_{n}\right)$ l'unica permutazione $\left(a_{1}^{\prime },a_{2}^{\prime },\ldots ,a_{n}^{\prime }\right)$ tale che $a_{1}^{\prime }\leq a_{2}^{\prime }\leq \cdots \leq a_{n}^{\prime }$. Ad esempio, $\left(6,9,4,5\right)$ ha come soluzione $\left(4,5,6,9\right)$. Una soluzione algoritmica al problema dell'ordinamento è quella dell'ordinamento a bolle, perché questo algoritmo produce una soluzione come uscita ogni volta che gli si somministra una istanza come entrata.
  
  ## Tipi di problemi computazionali
  
  Un problema decisionale è un problema computazionale in cui la risposta per ogni istanza è o "sì" o "no". Un esempio di problema decisionale è la verifica di primalità:
  
      "Dato un numero n intero positivo, determinare se n è un numero primo."
  
  Un problema decisionale è rappresentato tipicamente come l'insieme di tutte le istanze per le quali la risposta è sì. Ad esempio, la verifica di primalità può essere rappresentata come l'insieme infinito
  
      L = {2, 3, 5, 7, 11, ...}
  
  In un problema di ricerca, le risposte possono essere stringhe arbitrarie. Ad esempio, la fattorizzazione è un problema di ricerca in cui le istanze sono (rappresentazioni mediante stringhe di) interi positivi e le soluzioni sono (rappresentazioni mediante stringhe di) collezioni di primi.
  
  Un problema di ricerca è rappresentato come una relazione che consiste di tutte le coppie istanza-soluzione, chiamata relazione di ricerca. Ad esempio, la fattorizzazione può essere rappresentata come la relazione
  
      R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)...}
  
  che consiste di coppie di numeri (n, p), dove p è un fattore primo non banale di n.
  
  Un problema di conteggio chiede il numero di soluzioni a un dato problema di ricerca. Ad esempio, un problema di conteggio associato con la fattorizzazione è
  
      "Dato un intero positivo n, contare il numero di fattori primi non banali di n."
  
  Un problema di conteggio può essere rappresentare da una funzione f da {0, $1}^*$ agli interi non negativi. Per una relazione di ricerca R, il problema di conteggio associato a R è la funzione
  
      $f_R(x)$ = |{y: (x, y) ∈ R}|.
  
  Un problema di ottimizzazione che di trovare la soluzione "migliore possibile" tra l'insieme di tutte le soluzioni possibili a un problema di ricerca. Un esempio è il problema del massimo insieme indipendente:
  
      "Dato un grafo G, trovare un insieme indipendente di G di dimensione massima."
  
  I problemi di ottimizzazione possono essere rappresentati dalle loro relazioni di ricerca.
  
  In un problema di funzione di si aspetta un'unica uscita (di una funzione totale) per ogni entrata, ma l'uscita è più complessa di quella di un problema decisionale, cioè, non è semplicemente "sì" o "no". Uno degli esempi più famosi è il problema del commesso viaggiatore:
  
      "Data una lista di città e le distanze tra ciascuna coppia di città, trovare il più breve tragitto possibile che visita ciascuna città esattamente una volta e ritorna alla città di origine."
  
  È un problema NP-difficile in ottimizzazione combinatoria, importante nella ricerca operativa e nell'informatica teorica.
  
  ## Problemi di promessa
  
  Nella teoria della complessità computazionale, di solito si assume implicitamente che qualsiasi stringa in {0, $1}^*$ rappresenti un'istanza del problema computazionale in questione. Tuttavia, a volte non tutte le stringhe {0, $1}^*$ representano istanze valide, e si specifica un sottoinsieme proprio di {0, $1}^*$ come l'insieme di "istanze valide". I problemi computazionali di questo tipo sono chiamati problemi di promessa.
  
  Quello che segue è un esempio di un problema di promessa (decisionale):
  
      "Dato un grafo G, determinare se ogni insieme indipendente in G ha al più dimensione 5, o se G ha un insieme indipendente di dimensione almeno 10."
  
  Nel caso in esempio, le istanze valide sono i grafi G tali che ogni insieme indipendente in G abbia dimensione massima minore di 5 o maggiore di 10.
  
  I problemi di promessa decisionali sono rappresentati di solito come coppie di sottoinsiemi disgiunti $(L_{sì},$ $L_{no})$ di {0, $1}^*.$ Le istanze valide sono quelle in $L_{yes}$ ∪ $L_{no}.$ $L_{sì}$ e $L_{no}$ rappresentano le istanze la cui risposta è sì e no, rispettivamente.
  
  I problemi di promessa svolgono un ruolo importante in varie aree della complessità computazionale, compresa la difficoltà di approssimazione, la verifica di proprietà e i sistemi di prova interattivi.
  
  