Algorithmic Aspects of Problems Related to Optimization, Circuits, and Parameterized Complexity - Silva, Janio Carlos Nascimento; Souza, Uéverton dos Santos; Ochi, Luiz Satoru (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2022: Anais do XXXV Concurso de Teses e Dissertações, 2022)
This thesis investigates several aspects of computational problems related to circuits and neighborhood exploration. Supported by a vast literature, we explore notable trends in algorithms, optimization, and computational complexity; and we provide some results for each topic discussed. The thesis' contributions are organized into four projects: (i) the study of SUCCINCT MONOTONE CIRCUIT CERTIFICATION (SMCC); (ii) the study of BEST-CASE ENERGY COMPLEXITY IN SATISFYING ASSIGNMENTS (MINEC+M); (iii) the proposition of the Th-hierarchy as an alternative to the hierarchy of complexity classes so-called W-hierarchy; and (iv) the study of the MAXIMUM MULTI IMPROVEMENT problem. Over the course of these four projects, we develop polynomial and parameterized reductions, NP-completeness proofs, classical and parameterized complexity analysis, and implementations of exact algorithms and metaheuristics.