Satisfazibilidade probabilística / Probabilistic satisfiability

AUTOR(ES)

Glauber de Bona

DATA DE PUBLICAÇÃO

2011

RESUMO

Este trabalho estuda o problema da Satisfazibilidade Probabilística (PSAT), revendo a sua solução via programação linear, além de propor novos algoritmos para resolvê-lo através da redução ao SAT. Construímos uma redução polinomial do PSAT para o SAT, chamada de Redução Canônica, codificando operações da aritmética racional em bits, como variáveis lógicas. Analisamos a complexidade computacional dessa redução e propomos uma Redução Canônica de Precisão Limitada para contornar tal complexidade. Apresentamos uma Redução de Turing do PSAT ao SAT, baseada no algoritmo Simplex e na Forma Normal Atômica que introduzimos. Sugerimos modificações em tal redução em busca de eficiência computacional. Por fim, implementamos essas reduções a m de investigar o perl de complexidade do PSAT, observamos o fenômeno de transição de fase e discutimos as condições para sua detecção.

ASSUNTO(S)

lógica probabilística phase transition polynomial reduction probabilistic logic probabilistic satisfiability (psat) redução de turing redução polinomial satisfazibilidade (sat) satisfazibilidade probabilística (psat) satisfiability (sat) transição de fase turing reduction

Documentos Relacionados

• PROBABILISTIC OIL AND GAS RESERVES ASSESSMENT METHODOLOGY
• ANÁLISE PROBABILÍSTICA DE SEMÂNTICA LATENTE APLICADA A SISTEMAS DE RECOMENDAÇÃO
• ESTIMATIVA PROBABILÍSTICA DE RESERVAS RECUPERÁVEIS DE PETRÓLEO: MÉTODOS E APLICAÇÃO
• Avaliação teórica, numérica e probabilística de fundações tracionadas.
• Probabilistic analysis of durability applied to semi-trailer tank vehicle.