A lógica dos problemas computacionais

Abstract

Quando estudamos o assunto da NP-completude nos livros ou na internet, as reduções já aparecem prontas, e não é fácil entender como elas foram feitas. É a partir dessa dificuldade que nos orientamos para realizar este trabalho. De acordo com a teoria, existem alguns problemas que s ̃ao mais representativos para a classe NP: os chamados problemas NP-completos. Em certo sentido, esses problemas podem ser usados como uma linguagem na qual é possível descrever os outros problemas. Essa ́e uma das intuições por trás da definição de redução de problemas. E isso motiva uma investigação do assunto a partir do ponto de vista da lógica. A ideia chave é que com uma representação em linguagem lógica nós conseguimos descrever qualquer coisa, o que inclui descrever os problemas NP-completos. Isso nos leva ao primeiro objetivo deste trabalho: tentar entender a lógica dos problemas computacionais. E isso acaba levando ao segundo objetivo: tentar entender por que é mais fácil reduzir um problema para a l ́ogica (SAT) do que no sentido contrário. A ferramenta que nós desenvolvemos para alcançar esses objetivos foram os ”gadgetslógicos, que são as formas de induzir o funcionamento lógico que queremos ter. Utilizando os ”gadgets”lógicos, nós conseguimos formular reduções mais intuitivas para diversos problemas NP-completos, e muito semelhantes entre si. E por meio delas, nós demos um passo para alcançar o entendimento que motivou o trabalho.