Sharp-SAT
 | Este artigo não cita fontes confiáveis. (Julho de 2012) |
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]
- 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
Nota[editar | editar código-fonte]
- 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.
