Problema computazionale

Da Wikipedia, l'enciclopedia libera.

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 sosoluzione 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\le a_2^\prime\le \cdots\le 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 nuumeri 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\le a_2^\prime\le \cdots\le 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[modifica | modifica wikitesto]

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 è . 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. Adesempio, 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[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi 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."

Here, the valid instances are those graphs whose maximum independent set size is either at most 5 or at least 10.

I problemi di promessa decisionali sono rappresentati di solito come coppie di sottoinsiemi disgiunti (L, Lno) di {0, 1}*. Le istanze valide sono quelle in LyesLno. L e Lno rappresentano le istanze la cui risposta è 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[modifica | modifica wikitesto]