Complemento (complexidade)

Na teoria da complexidade computacional, o complemento de um problema de decisão é o problema de decisão resultante do reverso das respostas sim e não.Igualmente, se definimos problemas de decisão como um conjunto de cadeias finitas, então o complemento deste conjunto sobre um domínio fixo é seu problema-complemento.

Por exemplo, um problema importante é se um número é primo. Seu complemento é determinar se o número é um número composto (número que não é primo). Neste caso, o domínio do complemento é o conjunto de inteiros maiores do que um.

Existe uma Turing redução de todo problema para o seu complemento. A operação de complemento é uma Involução, que significa "se desfaz", ou o complemento do seu complemento é o problema original.

Isto pode se generalizar para o complemento de uma classe de complexidade, chamadas de classe de complemento, que é o conjunto dos complementos de cada problema na classe. Se uma classe é chamada C, seu complemento por convenção é chamado de co-C. Observe que isso não é o complemento da classes de complexidade propriamente dita como um conjunto de problemas, que conteria muito mais problemas.

Uma classe é dita fechada sob complemento se o complemento de qualquer problema na classe ainda pertencer à classe. Em razão do fato de que existem Turing-reduções de qualquer problema para o seu complemento, qualquer classe que é fechada sob Turing-redução é fechada sob complemento. Qualquer classe que é fechada sob complemento é equivalente ao seu complemento. No entanto, sob redução por mapeamento, muitas classes importantes, especialmente NP, acredita-se que são distintas de seu complemento (embora não tenha sido provado).

O fechamento de qualquer classe de complexidade sob uma Turing-redução é um superconjunto das classes que são fechadas sob complemento. O fecho sob complemento é a menor dessas classes. Se uma classe for operada pela interseção com o seu complemento, obtém-se um subconjunto (possivelmente vazio) que é fechado sob complemento.

Toda classe de complexidade determinística (DSAPCE(f(n)), DTIME(f(n)) para todo f(n)) é fechado sob complemento, pois pode ser adicionado um último passo ao algoritmo no qual se inverte a resposta. Isto não funciona para classes de complexidade não -determinísticas, pois se existe tanto caminhos que aceitam quanto caminhos que rejeitam, e todos os caminhos inverterem suas respostas, vão existir caminhos que aceitam e caminhos que rejeitam - consequentemente, a máquina aceita em ambos os casos.

Alguns dos mais surpreendentes resultados mostrados até agora mostraram que as classes de complexidade NL e SL são de fato fechadas sob seu complemento, enquanto que antes acreditava-se que elas não eram (veja Teorema de Immerman - Szelepcsényi). Este último tornou -se menos surpreendente quando sabemos que SL é igual a L, que é uma classe determinística.

Toda classe que é low é fechada sob complemento.