Complexidade de circuitos Booleanos

Abstract

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.