аЯрЁБс>ўџ 13ўџџџ0џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅСq`№ПP)bjbjqPqP.,::‰џџџџџџЄlllllll€d d d d € € D                j l l l l l l $_hЧ4 El           ll    е J J J   оl  l  j J   j J J llJ   ” €s„_ѓзd ~ ІJ j ы 0 J ћ$ ћJ ћlJ J         4                €€€фd €€€d €€€llllllџџџџ Resumo: Nas њltimas dщcadas, a resoluчуo de problemas de otimizaчуo combinatѓria considerados difэceis tornou-se um dos campos mais prolэficos da ciъncia da computaчуo. Diversos estudos tratam destes problemas tanto em uma perspectiva teѓrica quanto prсtica. Para alщm de resolver os problemas, a comunidade cientэfica tem-se dedicado em compreender os diferentes nэveis de dificuldade de problemas e como esses problemas comportam-se em termos de tratabilidade e estrutura. Nesta tese, apresentamos descobertas relacionadas a teoria da complexidade a partir de trъs diferentes perspectivas. Em um primeiro momento, dedicamos atenчуo a duas medidas de complexidade de circuitos: A Largura de Certificaчуo (certification-width) e a Complexidade de Energia. Ao tratar de circuitos monѓtonos, provamos a NP-completude de Certificaчуo Sucinta de um Circuito Monѓtono (SMCC) e de Complexidade de Energia de Melhor-Caso em Atribuiчѕes Satisfactэveis (MinEC+M), mesmo em casos onde os circuitos de entrada sуo planares. Provamos que ambos os problemas sуo W[1]-hard, mas que SMCC pertence a W[P], enquanto fornecemos um algoritmo XP para MinEC+M. Em seguida, para ambos os problemas foram elaboradas estratщgias de prщ-processamento dos grafos de entrada (baseado na estratщgia win-win, onde foi possэvel limitar a treewidth em circuitos com genus limitado; e a partir dessa estrutura resultante, apresentamos algoritmos FPT de programaчуo dinтmica baseado em decomposiчуo em сrvore destes grafos prщ-processados. Numa segunda perspectiva, apresentamos uma hierarquia de problemas parametrizados baseada na satisfabilidade de Circuitos Threshold – A Th-hierarquia. O estudo da Th-hierarquia buscou compreender possэveis lacunas existentes na W-hierarquia e perceber como as classes dessas hierarquias interagem. Provou-se que tais hierarquias colapsam nos nэveis mais altos (i.e. W[P] = Th[P]). Na sequъncia, ao estudar uma forma de converter circuitos threshold em circuitos booleanos convencionais com profundidade ѓtima, provou-se a possibilidade de construir uma rede de ordenaчуo AKS em tempo polinomial. Isso deu base para mostrar que Th[t] †" W[SAT], para todo nњmero natural t. Por fim, numa frente experimental, formalizamos um conceito de exploraчуo de vizinhanчa chamado Multi Improvement (alternativa aos tradicionais First Improvement and Best Improvement) e construэmos algoritmos de Programaчуo dinтmica para o Problema do Multi Improvement Mсximo, modelado como etapa interna de uma busca local sobre instтncias do TSP. Experimentos mostraram que esta abordagem provъ uma possibilidade de realizar buscas locais em vizinhanчa com rapidez e alta estabilidade. Palavras-chave: Otimizaчуo, Complexidade de Circuitos, Complexidade Parametrizada, W-hierarquia. Abstract: In the last few decades, the resolution of hard combinatorial optimization problems has become one of the most prolific fields in Computer Science. Several studies address these problems from both theoretical and practical perspectives. In addition, the scientific community has dedicated efforts to understand the different levels of hardness and how problems behave in terms of tractability and structure. In this thesis, we present discoveries related to complexity theory from three different perspectives. First, we address two measures in circuit complexity: The Certification-width and the Energy Complexity. When dealing with monotone circuits, we prove the NP-Completeness of Succinct Monotone Circuit Certification (SMCC) and Best-Case Energy Complexity in Satisfying Assignments (MinEC+M) even for planar circuits. We also prove that both problems are W[1]-hard, but SMCC belongs to W[P], while an XP-algorithm for MinEC+M is provided. After all, for both problems, we develop a pre-processing of input circuit (inspired by win-win approach strategy) where it was possible to prune graphs with bounded genus; this results in a structure whose treewidth is bounded. Hence, dynamic programming algorithms on tree decompositions were provided, solving the problems in FPT-time. In a second perspective, we present a hierarchy of classes of parameterized problems based on threshold circuit satisfiability – the Th-hierarchy. The study of Th-hierarchy aims to understand possible gaps in W-hierarchy and the interaction Th-hierarchy versus W-hierarchy levelwise. We show that the hierarchies collapse in high levels (i.e., W[P] = Th[P]). Next, we study ways to convert threshold circuits into Boolean circuits with optimal depth; thus, we demonstrate that it is possible to construct an AKS sorting network in polynomial-time. This supports to prove that Th[t] †" W[SAT], for every natural number t. Additionally, in an experimental front, we formalize the concept of neighborhood exploration called Multi Improvement (alternative to the traditional First Improvement and Best Improvement) and we build dynamic prog Q R Х й 5 a n М n u њ   ( : ? х ц `ižЇКМ  Ю№(-=w›opq€бвгсѓцѓтдадПдАдАдАдПдПдПдадПдПдПдПдадПдПдПдАдадŸда•„ h} и5OJQJ\^JmH sH hАn‡OJQJ^J hАn‡5CJOJQJ\^JaJhАn‡:CJOJQJ^JaJ hАn‡6CJOJQJ]^JaJhАn‡hАn‡CJOJQJ^JaJh} иh} и5OJQJ\^JhАn‡5OJQJ\^J0 R ц pqвгдежзийклмнопрсыььєPњњѕѕѕѕѕѕњњњњњњњњњњњњњњњњњѕѕѕ$a$$a$P)§сщъыьыь':CT›ТЮ Œ“љ ѓєz†ѓљ8JLNP<~ ьлЪП­˜˜u˜u˜_˜_˜_˜_˜u˜˜u˜u˜u˜u˜˜u˜u+h} иhАn‡:CJOJQJ^JaJmH sH .h} иhАn‡6CJOJQJ]^JaJmH sH h} иhАn‡mH sH (h} иhАn‡CJOJQJ^JaJmH sH "h} иCJOJQJ^JaJmH sH h} иh} иmH sH  hАn‡5OJQJ\^JmH sH  h} и5OJQJ\^JmH sH &h} иhАn‡5OJQJ\^JmH sH % ЊЪ( (A(ћ(ќ(§()O)P)ыгыбыЛыАы˜ыА.h} иhАn‡5CJOJQJ\^JaJmH sH h} иhАn‡mH sH +h} иhАn‡:CJOJQJ^JaJmH sH U.h} иhАn‡6CJOJQJ]^JaJmH sH (h} иhАn‡CJOJQJ^JaJmH sH  ramming algorithms to solve the Maximum Multi Improvement Problem modeled as an inner step of a local search for TSP instances. Experiments have shown that this approach provides a possibility to perform fast neighborhood searches with high stability. Keywords: Optimization, Circuit Complexity, Parameterized Complexity, W-hierarchy. Pќ(§(P)њњњ$a$,1hА‚. АЦA!Аn"Аn#n$n%ААаАа а†œf@ёџf Normal 1$*$A$3B*OJQJCJmHnHsHKHPJtH^JaJ_H9>A@ђџЁ> Fonte parсg. padrуoXi@ѓџГX  Tabela normal :V і4ж4ж laі ,k@єџС, Sem lista NўON Heading Є№Єx$OJQJCJPJ^JaJFB@F Corpo de textodЄЄŒ*/@* Lista^JH"@"H Legenda ЄxЄx $CJ6^JaJ].ўO2. Index $^J^ўOB^ Preformatted Text ЄЄOJQJCJPJ^JaJ‰,џџџџ Rц†p q в г д е ж з и й к л м н о п р с ы ь ь єa56‹˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€с P)PP)P)ТЯХи$1ЄВДЙ!%nsњ(:?CR`in{‰–\^gpžЇЕОZ\чьэј   ( ) , - 1 2 = ƒ ˆ ‰ ”   Œ“pyesz|•—цшTV57‹FhДЙnsžЉXZZ] ‹ ь  MONZMO=?‹3333‹ ‹хАn‡} иџ@€  ЦИ  @ 99‰P@PP$@PPP@џџUnknownџџџџџџџџџџџџGџ:рAxР џTimes New Roman5€Symbol3& џ:рCxР џArialIџрџxP!ПLiberation SerifiAR PL SungtiL GBTimes New RomanILohit DevanagariG& џрџxP!ПLiberation SansG5 џрџx@ПLiberation Mono"Aˆ Хhx›gB‹œЇ5T ƒ$5T $! 24 P №џџџџџџџџџџџџџџџџџџџџџ} иВџџHelioўџр…ŸђљOhЋ‘+'Гй0d˜ЄАМШи шє   , 8DLT\фNormalHelio2Microsoft Office Word@FУ#@@ОЛбз@ —l_ѓз5TўџеЭеœ.“—+,љЎ0ш hp|„Œ” œЄЌД М Щф$ ц  Tэtulo ўџџџўџџџ!"#$%&'ўџџџ)*+,-./ўџџџ§џџџ2ўџџџўџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџRoot Entryџџџџџџџџ РF`Z!„_ѓз4€1TableџџџџџџџџћWordDocumentџџџџџџџџ.,SummaryInformation(џџџџ DocumentSummaryInformation8џџџџџџџџџџџџ(CompObjџџџџџџџџџџџџuџџџџџџџџџџџџџџџџџџџџџџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџўџ џџџџ РF#Documento do Microsoft Office Word MSWordDocWord.Document.8є9Вq