Sharp-SAT

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou se(c)ção não cita fontes fiáveis e independentes (desde julho de 2012). Por favor, adicione referências e insira-as no texto ou no rodapé, conforme o livro de estilo. Conteúdo sem fontes poderá ser removido.

Na teoria da complexidade computacional, #SAT, ou Sharp-SAT é um problema de função relacionado com o problema da satisfabilidade booleana.

Conceito[editar | editar código-fonte]

O problema #SAT consiste em contar o número de resultados satisfatórios de uma dada fórmula booleana.

Notoriedade[editar | editar código-fonte]

É uma problema muito conhecido e integra a classe de problemas de mais importantes na teoria da complexidade computacional.

Características[editar | editar código-fonte]

É um problema P-completo já que qualquer máquina NP pode ser codificada em uma formula Booleana por um processo similar ao descrito no teorema de Cook-Levin, de tal modo que o número de atribuições satisfatórias da fórmula booleana é igual ao número de caminhos aceitáveis da máquina NP.

O problema #3SAT[editar | editar código-fonte]

Qualquer formula em SAT pode se escrita como uma forma normal conjuntiva, preservando o número de atribuições satisfatórias; sendo assim, os problemas #SAT e #3SAT são equivalentes e são ambos P-completos.

Ver também[editar | editar código-fonte]

Nota[editar | editar código-fonte]

Ícone de esboço Este artigo sobre Ciência (genérico) é um esboço. Você pode ajudar a Wikipédia expandindo-o.