Satisfatibilidade de circuitos threshold: uma ponte entre complexidade parametrizada e redes de ordenação

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSouza, Uéverton dos Santos-
Autor(es): dc.contributorRosseti, Isabel Cristina Mello-
Autor(es): dc.contributorMachado, Raphael Carlos Santos-
Autor(es): dc.contributorLopes, Bruno-
Autor(es): dc.creatorParanhos, Raffael Muralha-
Data de aceite: dc.date.accessioned2024-07-11T17:37:32Z-
Data de disponibilização: dc.date.available2024-07-11T17:37:32Z-
Data de envio: dc.date.issued2023-10-16-
Data de envio: dc.date.issued2023-10-16-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/30816-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/754093-
Descrição: dc.descriptionNeste trabalho será abordado inicialmente os principais conceitos de complexidade computacional. Começamos com as perguntas que motivam até hoje inúmeras pesquisas na área, passando pela complexidade parametrizada, que busca classificar problemas em um grão mais fino, até chegarmos na intratabilidade parametrizada e na W-hierarquia. Em seguida, os circuitos de ordenação serão introduzidos, culminando na rede AKS. A rede AKS é um circuito de ordenação com profundidade logarítmica, o que a torna interessante do ponto de vista teórico. Infelizmente a rede AKS possui inúmeras limitações para sua implementação devido a constantes gigantescas. Propomos então, uma família de classes de complexidades baseadas em circuitos de limiar (threshold), denominada Th-hierarquia, de forma a fazer uma série de questionamentos quanto a W-hierarquia. Alguns desses questionamentos serão respondidos, e tais respostas utilizarão transformações de circuitos threshold para circuitos booleanos como demonstrações. Como ferramenta para essas transformações utilizaremos circuitos de ordenação e, principalmente, a rede AKS. Existe uma restrição quanto ao tempo dessas transformações, posto isto, obtemos colateralmente uma análise da complexidade da construção da rede AKS e concluímos que a mesma pode ser construída em tempo polinomial. Como consequência mostramos que algumas classes da W-hierarquia colapsam com classes da TH-hierarquia proposta-
Descrição: dc.descriptionIn this paper will be initially approached the main concepts of computational complexity, beginning with the questions that motivate until nowadays countless searches in this area, going by parametrized complexity that searches for classifying problems in a smaller grain, until we get in a parametrized intractability and in W-hierarchy. Then, the sorting network are going to be introduced, culminating in AKS network. The AKS network is a sorting network with logarithmic depth, which turns it to be very interesting in a theoretical point of view. Unfortunately, AKS network have countless limitations to your implementation due to your enormous constants. It’s proposed then, a complexities class family based on threshold circuits, denomina- ted Th-hierarchy, in order to do a series of questionings as to W-hierarchy. Some of this questioning are going to be responded, and such answers will utilize threshold circuits transformations to boolean circuits as demonstrations. As a tool for this transformati- ons we are going to utilize sorting network, and mainly the AKS network. There is a restriction about the time of this transformations, therefore, we collaterally obtain an analysis of AKS network and conclude that it can be constructed in polynomial time. As consequence wes how that some W-hierarchy classes colapse with TH-hierarchy classes proposed-
Descrição: dc.description44 p.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectComplexidade computacional-
Palavras-chave: dc.subjectIntratabilidade parametrizada-
Palavras-chave: dc.subjectRedes de ordenação-
Palavras-chave: dc.subjectW-hierarquia-
Palavras-chave: dc.subjectCircuitos threshold-
Palavras-chave: dc.subjectRede AKS-
Palavras-chave: dc.subjectComplexidade computacional-
Palavras-chave: dc.subjectCircuito de ordenação-
Palavras-chave: dc.subjectIntratabilidade parametrizada-
Palavras-chave: dc.subjectComputational complexity-
Palavras-chave: dc.subjectParameterized intractability-
Palavras-chave: dc.subjectSorting network-
Palavras-chave: dc.subjectW-hierarchy-
Palavras-chave: dc.subjectThreshold circuits-
Palavras-chave: dc.subjectAKS networks-
Título: dc.titleSatisfatibilidade de circuitos threshold: uma ponte entre complexidade parametrizada e redes de ordenação-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.