Nella teoria della complessità computazionale, il complemento di un problema decisionale è il problema risultante dall'inversione delle risposte sì e no. 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. Wikipedia