Satisfazibilidade probabilística

• Ano de defesa: 2011
• Autor(a) principal: De Bona, Glauber
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Portuguê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
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-02062011-181639/

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.