Complemento (complexidade): diferenças entre revisões

Origem: Wikipédia, a enciclopédia livre.
Conteúdo apagado Conteúdo adicionado
nova página: Na teoria da complexidade computacional, o complemento de um problema de decisão é o problema de decisão resultante do reverso das respostas ''...
(Sem diferenças)

Revisão das 16h44min de 3 de julho de 2016

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.[1]Equivalente, se definimos problemas de decisão como um conjunto de strings finitas, então o complemento deste conjunto sobre um domínio fixo é seu complemento.[2]

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.[3]

Existe uma Turing redução de todo problema para o seu complemento.[4] 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 do complemento de todo problema na classe.[5] Se uma classe é chamada C, seu complemento por convenção é chamado de co-C. Observe que a classe de complexidade por si própria não é um conjunto de problemas, conteria muito mais problemas.

Uma classe é dita fechada sob complemento se o complemento de qualquer problema na classe ainda pertencer a classe.[6] Pois existem Turing reduções de qualquer problema para o seu complemento, qualquer classe que é Turing redutível é fechada sob complemento. Qualquer classe que é fechada sob complemento é equivalente ao complemento de sua classe. No entanto, sob redução por mapeamento, classes mais importantes, especialmente NP, acredita-se que a classe do seu complemento seja diferente (embora não tenha sido provado).[7]

O fechamento sob qualquer classe de complexidade sob uma Turing redução é um superconjunto das classes que são fechadas sob complemento. O fecho sob complemento é o menor desta classe. Se uma classe é a 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,[8] pois pode ser adicionado um último passo ao algoritmo no qual o reverso é a resposta. Isto não funciona para classes de complexidade não - determinísticas, pois se existe dois caminhos que aceitam e rejeitam, e todos os caminhos inverterem suas respostas, vão existir caminhos que são de aceitação e rejeição - consequentemente , a máquina aceita em ambos os casos.

Alguns dos mais surpresos 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.

Uma seção

Este é um texto de demonstração e você deve substituí-lo pelo seu conteúdo. Enquanto isso, aqui vão algumas dicas:

Para criar uma lista de itens, use um asterisco no início de cada linha:

  • Um item
  • Outro item

Para que uma palavra tenha link ou ligação para outro artigo, só colocá-la entre colchetes assim: um link.

O itálico é para destacar palavras em idioma estrangeiro, por exemplo software.

Uma lista numerada começa cada item com cerquilha, assim:

  1. Um item
  2. Outro item

Todo artigo deve ter referências ou fontes para comprovar a informação. Para adicionar uma referência, só adicionar: ou se é para um website ou sítio:

Para ver como seu artigo está antes de publicá-lo, clique no botão Mostrar previsão. Se tudo estiver pronto, clique então em Salvar página ou Gravar página para publicar seu artigo!

Exemplo de outra seção

Aqui vai o texto de outra seção caso precise!

Referências

  1. Itô, Kiyosi (1 de janeiro de 1993). Encyclopedic Dictionary of Mathematics (em inglês). [S.l.]: MIT Press. ISBN 9780262590204 
  2. Schrijver, Alexander (7 de julho de 1998). Theory of Linear and Integer Programming (em inglês). [S.l.]: John Wiley & Sons. ISBN 9780471982326 
  3. Homer, Steven; Selman, Alan L. (2011). Computability and Complexity. [S.l.]: Springer. ISBN 9781461406815. Verifique |isbn= (ajuda) 
  4. Singh, Arindama (30 de abril de 2009). Elements of Computation Theory (em inglês). [S.l.]: Springer Science & Business Media. ISBN 9781848824973 
  5. Bovet, Daniele; Crescenzi, Pierluigi (1994). Introduction to the Theory of Complexity. [S.l.]: Prentice Hall International Series in Computer Science, Prentice Hall. pp. 133 –134. ISBN 9780139153808. Verifique |isbn= (ajuda) 
  6. Vollmer, Heribert (1999). Introduction to Circuit Complexity: A Uniform. [S.l.]: Texts in Theoretical Computer Science. An EATCS Series, Springer. 113 páginas. ISBN ISBN 9783540643104. Verifique |isbn= (ajuda) 
  7. Weneger, Ingo; Pruim, R. (2005). Complexity Theory: Exploring the Limits of Efficient Algorithms. [S.l.]: Springer. 66 páginas. ISBN 9783540274773. Verifique |isbn= (ajuda) 
  8. Ausiello, Giorgio (1999). Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. [S.l.]: Springer. 189 páginas. ISBN 9783540654315