| Popis: |
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. |
