| dc.contributor | Marchi, Jerusa | |
| dc.contributor | Universidade Federal de Santa Catarina | |
| dc.creator | Peres, Léo Vieira | |
| dc.date | 2018-07-08T20:02:01Z | |
| dc.date | 2018-07-08T20:02:01Z | |
| dc.date | 2017-11-17 | |
| dc.date.accessioned | 2018-10-31T21:23:11Z | |
| dc.date.available | 2018-10-31T21:23:11Z | |
| dc.identifier | https://repositorio.ufsc.br/handle/123456789/187863 | |
| dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/1790646 | |
| dc.description | TCC(graduação) - Universidade Federal de Santa Catarina. Centro Tecnológico. Ciências da Computação. | |
| dc.description | Podemos dizer que complexidade computacional busca descobrir o quão dificil é resolver problemas computacionais. Por exemplo, uma forma equivalente de descrever o problema em aberto mais importante da teoria da computação, P vs NP, é perguntar se o problema da sastifazibilidade booleana, denominado SAT, necessita de tempo "mais do que polinomial" para ser decidido no caso geral. Isto se deve ao fato que SAT pertence à classe de problemas NP-completos, que são problemas em NP que têm um algoritmo de tempo polinomial se e somente se todos os problemas em NP também têm. No entanto, até agora não se obteve muito sucesso em provar limitantes inferiores para problemas NP-completos, tanto que ainda é um problema em aberto determinar se SAT necessita de mais do que \Omega(n^2) passos de uma máquina de Turing determinística para ser decidido. Classificar problemas pela sua complexidade de circuitos é uma duas principais frentes de pesquisa para provar limitantes inferior de problemas computacionais e por muitos anos pesquisadores acreditaram que complexidade de circuitos era a chave para provar problemas como P vs NP, onde a complexidade de circuito de um problema é basicamente o número mínimo de portas lógicas necessárias para implementar um circuito que decida este problema. Nós veremos a técnica de restrição e projeção aleatória que obteve sucesso em provar limitantes inferiores para classes bem estritas de circuitos, e logo depois também veremos que estas mesmas técnicas caem no escopo das provas naturais de Razborov e Rudich e portanto são limitadas demais para resolver a questão P vs NP e outros grandes problemas em aberto na área da complexidade computacional. Entretanto, alguns resultados recentes que ligam algoritmos eficientes e limitantes inferiores conseguiram provar limitantes inferiores que estavam em abertos desde os anos 80. Acredita-se que esta ligação entre algoritmos e limitantes inferiores possam a vir superar a barreira das provas naturais e portanto abriram caminho para novos tópicos de pesquisa. | |
| dc.format | 121 f. | |
| dc.format | application/pdf | |
| dc.language | pt_BR | |
| dc.publisher | Florianópolis, SC. | |
| dc.subject | complexidade computacional | |
| dc.subject | complexidade de circuitos | |
| dc.title | Complexidade de circuitos Booleanos | |
| dc.type | Tesis | |
