co-NP-completo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita fontes fiáveis e independentes, mas que não cobrem todo o conteúdo (desde dezembro de 2011). Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Trechos sem fontes poderão ser removidos.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing.
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde dezembro de 2011).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.
Ambox grammar.svg
Esta página ou secção precisa de correção ortográfico-gramatical.
Pode conter incorreções textuais, podendo ainda necessitar de melhoria em termos de vocabulário ou coesão, para atingir um nível de qualidade superior conforme o livro de estilo da Wikipédia. Se tem conhecimentos linguísticos, sinta-se à vontade para ajudar.

Na teoria da complexidade, problemas computacionais co-NP-completos são os mais difíceis problemas em co-NP,no sentido de que são os mais propensos a não serem P. Se existisse uma forma de resolver um problema co-NP-completo rapidamente, então esse algoritmos poderia ser usado para resolver todos os problemas co-NP rapidamente.

Um problema Co-NP-completo é o complemento de um problema NP-completo. Existem alguns problemas que estão em NP e co-NP, contudo não se sabe se essas classe são iguais, embora a desigualdade seja o pensamento mais provável. Veja co-NP e NP-complete para mais detalhes.

Fortune mostrou em 1979 que se alguma sparse language é co-NP-completo (ou apenas co-NP-difícil), então P = NP,[1] um fundamento essencial para o Mahaney's theorem.

Definição Formal[editar | editar código-fonte]

Um Problema de decisão C é co-NP-completo se esta em co-NP e se qualquer problema em co-NP é reduzido em tempo polinomial a ele. Isso significa que para cada problema Co-NP L, existe um algoritmo em tempo polinomial que pode transforma qualquer instancia de L em uma instancia de C com o mesmo valor verdade. Como consequência, se nos temos um algoritmo em tempo polinomial para C, nos poderíamos resolver qualquer problema em tempo polinomial.

Exemplo[editar | editar código-fonte]

Um exemplo simples de um problema co-NP-completo é tautologia, o problema de determinar se uma formula booleana é uma tautologia; isso é, se todos as possíveis combinações de valores atribuídos as variáveis produz uma afirmação verdadeira. Isso esta intimamente relacionado ao Problema de satisfatibilidade booleana, que pergunta se existe ao menos uma combinação de atribuição que satisfaz a formula. Observe que o problema da tautologia para formulas booleanas positivas permanece Co-NP-completo, embora o problema da satisfatibilidade seja trivial, como cada uma das formulas deve ser satisfativel.

Referencias[editar | editar código-fonte]

  1. S. Fortune. A note on sparse complete sets. SIAM Journal on Computing, volume 8, issue 3, pp.431–433. 1979.

Predefinição:Classesdecomplexidade