Título: Parameterized Complexity of Some Prefix Fragments of First-Order Logic

Data: 15/12/2017 Horário: 09:30h Local: Sala de Seminários

Resumo:

The Theory of Parameterized Complexity has benefited from results of Logic both by receiving computational problems of general interest and by the formal organization of fundamental concepts and ideas in this branch of Computational Complexity. In this work, we advance into parameterized versions of satisfiability problem for First-order Logic. The satisfiability problem is decidable for many prefix fragments of First-Order Logic. These languages are useful for defining many real problems, and most SAT problems have high computational complexity, but for some fragments its complexity is modest. We investigate the parameterized complexity of these problems considering parameters from the vocabulary and from their proper prefix. We will see that for all modest complexity prefix classes a fixed parameter tractable algorithm exists. On the other hand, we developed a study on parameterized classes of circuits with the objective of establishing capture results by a logical formalism. In particular, we have attempted to establish the logical formalism identified by parameterized versions of class AC$^0$, TC$^0$, and NC$^1$.

Banca:

• Profª. Drª. Ana Tereza Martins de Castro (MDCC/UFC - Orientador)
• Prof. Dr. Francicleber Ferreira Martins (UFC - Coorientador)
• Prof. Dr. Edward Hermann Haeusler (PUC/RJ)
• Prof. Dr. João Fernando Lima Alcântara (MDCC/UFC)