Complemento (complessità): differenze tra le versioni
←Nuova pagina: Nella teoria della complessità computazionale, il '''complemento''' di un problema decisionale è il problema risultante dall'inversione delle risposte ''sì''... |
(Nessuna differenza)
|
Versione delle 19:22, 15 ott 2015
Nella teoria della complessità computazionale, il complemento di un problema decisionale è il problema risultante dall'inversione delle risposte sì e no.[1] In maniera equivalente, se definiamo un problema decisionale come un insieme di stringhe finite, allora il complemento di questo insieme su un certo dominio è il suo problema complementare.[2]
Per esempio, un importante problema è stabilire se un numero sia o no primo. Il suo complemento è di determinare se un numero è composto (ovvero, se non è primo). In questo caso, il dominio del complemento è l'insieme di tutti gli interi tranne uno.[3]
Esiste una Turing-riduzione da ogni problema al suo complemento.[4] L'operazione complementare è involuzione, ovvero il complemento del complemento del problema originale.
Le precedenti nozioni possono essere estese al livello delle classi di complessità, ottenendo così il concetto di classe complemento (o classe complementare), che è l'insieme dei complementi di tutti i problemi della classe data.[5] Presa una classe C qualsiasi, il suo complemento viene convenzionalmente indicato con co-C. Da notare che una classe complemento non è il complemento della classe in quanto insieme di problemi, il quale conterrebbe un numero di problemi assai maggiore.
Una classe di complessità è detta essere chiusa rispetto al complemento se il complemento di ciascun problema appartenente alla classe appartiene alla classe stessa.[6] Dato che esiste una Turing-riduzione da ogni problema al suo complemento, ogni classe che è chiusa rispetto alle Turing-riduzioni è chiusa rispetto al complemento. Ogni classe chiusa rispetto al complemento è uguale alla sua classe complementare. Per quanto riguarda le classi chiuse rispetto alle cosiddette riduzioni "many-one", invece, si crede che molte classi importanti (tra cui NP, in particolare) siano distinte dal proprio complemento (nello specifico, co-NP), anche se non è stato provato.[7]
Ogni classe di complessità deterministica (DSPACE(f(n)), DTIME(f(n)), per ogni f(n)) è chiusa rispetto al complemento,[8] perché si può semplicemente aggiungere un ultimo passo all'algoritmo che inverte la risposta. Questo espediente non funziona per le classi di complessità non deterministiche: dati, infatti, due percorsi computazionali, uno accettante ed uno respingente, pur facendo in modo che essi neghino il proprio risultato, continueranno ad esistere due percorsi uno dei quali sarà accettante; quindi la macchina, in maniera non deterministica, troverà ancora il modo di accettare ed il problema continuerà ad avere esito positivo (e, di conseguenza, non rappresenterà il complemento del problema di partenza).
Note
- ^ (EN) Kiyosi Itô, Encyclopedic Dictionary of Mathematics, Volume 1, MIT Press, 1993.
- ^ (EN) Alexander Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, 1998..
- ^ (EN) Computability and Complexity Theory, Springer, 2011..
- ^ (EN) Arindama Singh, Elements of Computation Theory, Springer, 2009..
- ^ (EN) Introduction to the Theory of Complexity, Prentice Hall, 1994, pp. 133–134..
- ^ (EN) Heribert Vollmer, Introduction to Circuit Complexity: A Uniform Approach, Springer, 1999..
- ^ (EN) Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, 2005..
- ^ (EN) Giorgio Ausiello, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, 1999..
