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
- Soluzione: Una permutazione della successione in entrata tale che
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 l'unica permutazione tale che . Ad esempio, ha come soluzione . 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
- fR(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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Magnifying_glass_icon_mgx2.svg/18px-Magnifying_glass_icon_mgx2.svg.png)
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 (Lsì, Lno) di {0, 1}*. Le istanze valide sono quelle in Lyes ∪ Lno. Lsì e Lno 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.
Bibliografia
- 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.
Altri progetti
Altri progetti
- Wikimedia Commons
Wikimedia Commons contiene immagini o altri file su problema computazionale
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)