Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Souza, Uéverton dos Santos | - |
Autor(es): dc.contributor | Rosseti, Isabel Cristina Mello | - |
Autor(es): dc.contributor | Machado, Raphael Carlos Santos | - |
Autor(es): dc.contributor | Lopes, Bruno | - |
Autor(es): dc.creator | Paranhos, Raffael Muralha | - |
Data de aceite: dc.date.accessioned | 2024-07-11T17:37:32Z | - |
Data de disponibilização: dc.date.available | 2024-07-11T17:37:32Z | - |
Data de envio: dc.date.issued | 2023-10-16 | - |
Data de envio: dc.date.issued | 2023-10-16 | - |
Fonte completa do material: dc.identifier | http://app.uff.br/riuff/handle/1/30816 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/754093 | - |
Descrição: dc.description | Neste 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.description | In 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.description | 44 p. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Direitos: dc.rights | Open Access | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | Complexidade computacional | - |
Palavras-chave: dc.subject | Intratabilidade parametrizada | - |
Palavras-chave: dc.subject | Redes de ordenação | - |
Palavras-chave: dc.subject | W-hierarquia | - |
Palavras-chave: dc.subject | Circuitos threshold | - |
Palavras-chave: dc.subject | Rede AKS | - |
Palavras-chave: dc.subject | Complexidade computacional | - |
Palavras-chave: dc.subject | Circuito de ordenação | - |
Palavras-chave: dc.subject | Intratabilidade parametrizada | - |
Palavras-chave: dc.subject | Computational complexity | - |
Palavras-chave: dc.subject | Parameterized intractability | - |
Palavras-chave: dc.subject | Sorting network | - |
Palavras-chave: dc.subject | W-hierarchy | - |
Palavras-chave: dc.subject | Threshold circuits | - |
Palavras-chave: dc.subject | AKS networks | - |
Título: dc.title | Satisfatibilidade de circuitos threshold: uma ponte entre complexidade parametrizada e redes de ordenação | - |
Tipo de arquivo: dc.type | Trabalho de conclusão de curso | - |
Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: