A lógica dos Problemas Computacionais

Abstract

Quando estudamos o assunto da NP-completude nos livros ou na internet, as redu ̧c ̃oes j ́a aparecem prontas, e n ̃ao ́e f ́acil entender como elas foram feitas. E ́ 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 ́e poss ́ıvel descrever os outros problemas. Essa ́e uma das intui ̧c ̃oes por tr ́as da defini ̧c ̃ao de redu ̧c ̃ao de problemas. E isso motiva uma investiga ̧c ̃ao do assunto a partir do ponto de vista da l ́ogica. A ideia chave ́e que com uma representa ̧c ̃ao em linguagem l ́ogica n ́os conseguimos descrever qualquer coisa, o que inclui descrever os problemas NP-completos. Isso nos leva ao primeiro objetivo deste trabalho: tentar entender a l ́ogica dos problemas computacionais. E isso acaba levando ao segundo objetivo: tentar entender por que ́e mais f ́acil reduzir um problema para a l ́ogica (SAT) do que no sentido contr ́ario. A ferramenta que n ́os desenvolvemos para alcan ̧car esses objetivos foram os ”gadgets”l ́ogicos, que s ̃ao as formas de induzir o funcionamento l ́ogico que queremos ter. Utilizando os ”gadgets”l ́ogicos, n ́os conseguimos formular redu ̧c ̃oes mais intuitivas para diversos problemas NP-completos, e muito semelhantes entre si. E por meio delas, n ́os demos um passo para alcan ̧car o entendimento que motivou o trabalho.