Algorithmic Aspects of Problems Related to Optimization, Circuits, and Parameterized Complexity

  • Janio Carlos Nascimento Silva UFF / IFTO
  • Uéverton dos Santos Souza UFF
  • Luiz Satoru Ochi UFF

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.

Palavras-chave: Optimization, Circuit Complexity, Parameterized Complexity, W-hierarchy

Referências

Dinesh, K., Otiv, S., and Sarma, J. (2020). New bounds for energy complexity of boolean functions. Theoretical Computer Science.

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.
Publicado
31/07/2022
SILVA, Janio Carlos Nascimento; SOUZA, Uéverton dos Santos; OCHI, Luiz Satoru. Algorithmic Aspects of Problems Related to Optimization, Circuits, and Parameterized Complexity. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 35. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 21-30. ISSN 2763-8820. DOI: https://doi.org/10.5753/ctd.2022.223305.