Algorithmic Aspects of Problems Related to Optimization, Circuits, and Parameterized Complexity
Resumo
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.
Referências
Downey, R. G. and Fellows, M. R. (2012). Parameterized complexity. Springer Science & Business Media.
Kanj, I., Thilikos, D. M., and Xia, G. (2017). On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability. Information and Computation, 257:139–156.
Lennie, P. (2003). The cost of cortical computation. Current biology, 13(6):493–497.
Paterson, M. S. (1990). Improved sorting networks with o (log n) depth. Algorithmica, 5(1):75–92.
Robertson, N. and Seymour, P. D. (1984). Graph minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49–64.
Silva, J. C. N. (2021). Algorithmic Aspects of Problems Related to Optimization, Circuits, and Parameterized Complexity. PhD thesis, Universidade Federal Fluminense, Niterói, RJ.
Uchizawa, K., Douglas, R., and Maass, W. (2006). On the computational power of threshold circuits with sparse activity. Neural Computation, 18(12):2994–3008.
