Sharp-SAT – Wikipédia, a enciclopédia livre

Este artigo não cita fontes confiáveis. Ajude a inserir referências. Conteúdo não verificável pode ser removido.—Encontre fontes: ABW  • CAPES  • Google (N • L • A) (Julho de 2012)

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

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

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

É 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.

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.

• Complexidade
• Sistemas formais
• Lista de termos referentes ao tema
• Complexidade Logarítmica
• Complexidade (informática)
• Forma Normal Negativa
• Forma Normal Disjuntiva
• Forma Normal Algébrica
• Cláusula de Horn

• Este artigo foi inicialmente traduzido, total ou parcialmente, do artigo da Wikipédia em inglês cujo título é «Sharp-SAT», especificamente desta versão.

Este artigo sobre ciência é um esboço. Você pode ajudar a Wikipédia expandindo-o. v d e