Loading AI tools
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).
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
