Complemento (complessità)
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 è l'involuzione, ovvero il 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 della 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[modifica | modifica wikitesto]
- ^ (EN) Kiyosi Itô, Encyclopedic Dictionary of Mathematics, Volume 1, MIT Press, 1993, p. 269, ISBN 9780262590204.
- ^ (EN) Alexander Schrijver, Theory of Linear and Integer Programming, Wiley Series in Discrete Mathematics & Optimization, John Wiley & Sons, 1998, p. 19, ISBN 9780471982326.
- ^ (EN) Steven Homer e Alan L. Selman, Computability and Complexity Theory, Texts in Computer Science, Springer, 2011, ISBN 9781461406815.
- ^ (EN) Arindama Singh, Elements of Computation Theory, Texts in Computer Science, Springer, 2009, p. 287 (esercizio 9.10), ISBN 9781848824973.
- ^ (EN) Daniele Bovet e Pierluigi Crescenzi, Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, Prentice Hall, 1994, pp. 133–134, ISBN 9780139153808.
- ^ (EN) Heribert Vollmer, Introduction to Circuit Complexity: A Uniform Approach, Texts in Theoretical Computer Science. An EATCS Series, Springer, 1999, p. 113, ISBN 9783540643104.
- ^ (EN) R. Pruim e Ingo Wegener, Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, 2005, p. 66, ISBN 9783540274773.
- ^ (EN) Giorgio Ausiello, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, 1999, p. 189, ISBN 9783540654315.
