You are here

PSAT

Este projeto estuda o problema da Satisfazibilidade Probabilísitica (PSAT), procurando desenvolver novos algoritmos que decidam o problema, além de investigar seu perfil de complexidade. Nesta página estão disponíveis alguns softwares resultantes da implementação de direfentes técnicas aordadas para resolver o PSAT:
- PSATtoSAT decide o PSAT fazendo uma redução polinomial ao SAT (problema da Satisfazibilidade Booleana). Assim, decidindo a satisfazilibidade de uma instância SAT, decide-se a satisfazibilidade probabilística de uma instância PSAT.
- PsatColGen ataca o PSAT usando técnicas de programação linear, adpatando o algoritmo Simplex com o método Geração de Colunas para resolver instâncias na forma normal. A cada iteração, instâncias SAT são decididas para gerar novas colunas - por isso temos uma redução de turing do PSAT ao SAT.

Clique aqui para ser redirecionado à página de download.