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 ${\displaystyle \left(a_{1},a_{2},\ldots ,a_{n}\right)}$

Soluzione: Una permutazione ${\displaystyle \left(a_{1}^{\prime },a_{2}^{\prime },\ldots ,a_{n}^{\prime }\right)}$ della successione in entrata tale che ${\displaystyle 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 ${\displaystyle \left(a_{1},a_{2},\ldots ,a_{n}\right)}$ l'unica permutazione ${\displaystyle \left(a_{1}^{\prime },a_{2}^{\prime },\ldots ,a_{n}^{\prime }\right)}$ tale che ${\displaystyle a_{1}^{\prime }\leq a_{2}^{\prime }\leq \cdots \leq a_{n}^{\prime }}$. Ad esempio, ${\displaystyle \left(6,9,4,5\right)}$ ha come soluzione ${\displaystyle \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.

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.

Lo stesso argomento in dettaglio: Problema 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.

• Shimon Even, Alan L. Selman e Yacov Yacobi, The complexity of promise problems with applications to public-key cryptography, in Information and Control, vol. 61, n. 2, 1984, 159–173, DOI:10.1016/S0019-9958(84)80056-X.
• Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 978-0-521-88473-0.
• Oded Goldreich e Avi Wigderson, IV.20 Computational Complexity, in Timothy Gowers, June Barrow-Green e Imre Leader (a cura di), The Princeton Companion to Mathematics, Princeton University Press, 2008, 575–604, ISBN 978-0-691-11880-2.

• Wikimedia Commons contiene immagini o altri file su problema computazionale

Portale Informatica

Portale Matematica