Os Limites da Computação Eficiente
Coleção Escola de Lógica Matemática
JOÃO CARLOS MOREIRA
Doutor em Matemática
Universidade Federal de Uberlândia
Copyright©2013-2025 Coleção Escola de Lógica Matemática. Todos os direitos reservados.
Imagine ter nas mãos um quebra-cabeça de mil peças. Você sabe que existe uma solução — a imagem completa na caixa confirma isso. Mas quantos movimentos serão necessários? Quantas tentativas até encontrar o encaixe perfeito? Este desafio aparentemente simples esconde uma das questões mais profundas da matemática e da computação: qual é a diferença fundamental entre resolver um problema e verificar sua solução? Bem-vindo ao fascinante universo da complexidade computacional, onde exploraremos os limites do que pode ser calculado eficientemente e descobriremos por que algumas perguntas aparentemente simples desafiam as mentes mais brilhantes há décadas.
A complexidade computacional surgiu quando matemáticos e cientistas da computação perceberam que não bastava saber se um problema tinha solução — era crucial entender quanto tempo e recursos seriam necessários para encontrá-la. Na década de 1960, enquanto os primeiros computadores ocupavam salas inteiras, pesquisadores começaram a notar padrões intrigantes: alguns problemas podiam ser resolvidos rapidamente mesmo com entradas enormes, enquanto outros se tornavam impossíveis na prática com apenas algumas dezenas de elementos.
Como comparar a eficiência de diferentes algoritmos? A resposta está na análise assintótica — estudamos como o tempo cresce conforme o tamanho da entrada aumenta. Um algoritmo que demora n² passos é fundamentalmente diferente de um que precisa de 2ⁿ passos. Para entradas pequenas, a diferença pode ser imperceptível, mas quando n = 100, o primeiro termina em segundos enquanto o segundo demoraria mais que a idade do universo!
Para estudar complexidade com rigor, precisamos de um modelo matemático de computação. A máquina de Turing, proposta por Alan Turing em 1936, serve perfeitamente a este propósito. Apesar de sua simplicidade conceitual — uma fita infinita, um cabeçote que lê e escreve símbolos, e um conjunto de regras — ela captura a essência de qualquer computação possível. Todo computador moderno, smartphone ou supercomputador pode ser simulado por uma máquina de Turing.
A grande divisão na complexidade computacional ocorre entre algoritmos de tempo polinomial (O(nᵏ) para algum k fixo) e tempo exponencial (O(2ⁿ) ou pior). Algoritmos polinomiais são considerados eficientes ou tratáveis — mesmo que n¹⁰⁰ pareça grande, cresce incomparavelmente mais devagar que 2ⁿ. Esta distinção não é apenas teórica: ela determina o que é viável calcular no mundo real.
Embora o tempo seja o recurso mais estudado, a complexidade computacional também analisa espaço (memória), comunicação, energia e até mesmo aleatoriedade. Um algoritmo pode ser rápido mas consumir memória exponencial, tornando-o impraticável. O trade-off entre diferentes recursos é uma arte delicada no design de algoritmos.
A complexidade computacional não é apenas teoria abstrata — ela molda nossa vida digital diária. Quando você faz uma compra online, algoritmos eficientes processam seu pagamento em segundos. Quando o GPS calcula a melhor rota, usa algoritmos de grafos otimizados. E quando sua senha protege seus dados, a segurança depende fundamentalmente da dificuldade computacional de certos problemas matemáticos.
Os problemas computacionais são organizados em classes baseadas nos recursos necessários para resolvê-los. P contém problemas solúveis em tempo polinomial. NP engloba problemas cujas soluções podem ser verificadas rapidamente. PSPACE inclui problemas solúveis com espaço polinomial. Cada classe captura uma noção diferente de dificuldade computacional.
A tese original de Church-Turing afirma que qualquer função computável pode ser calculada por uma máquina de Turing. A versão estendida vai além: qualquer processo físico eficiente pode ser simulado eficientemente por uma máquina de Turing probabilística. Esta conjectura profunda conecta a física fundamental com a teoria da computação, sugerindo que as leis da natureza respeitam limites computacionais.
Este capítulo estabeleceu os fundamentos para nossa jornada pelo mundo das classes P e NP. Vimos como medir e classificar a dificuldade computacional, conhecemos a máquina de Turing como modelo universal, e entendemos a distinção crucial entre tempo polinomial e exponencial. Nos próximos capítulos, mergulharemos nas classes específicas que definem os limites do computável, começando pela classe P — o reino dos problemas que sabemos resolver eficientemente. Prepare-se para descobrir por que alguns problemas são fáceis, outros parecem impossíveis, e por que a fronteira entre eles esconde um dos maiores mistérios da matemática!
Se o universo computacional fosse um reino, a classe P seria sua província mais bem-comportada e previsível. Aqui vivem os problemas que podemos resolver eficientemente — aqueles para os quais conhecemos algoritmos que terminam em tempo razoável, mesmo para entradas gigantescas. Ordenar bilhões de números, encontrar o menor caminho em um mapa com milhões de estradas, multiplicar matrizes enormes — todos esses desafios, apesar de sua aparente complexidade, pertencem a P. Neste capítulo, exploraremos esta classe fundamental, descobrindo o que torna um problema tratável e por que P é considerada a fronteira da computação prática.
A classe P consiste de todos os problemas de decisão que podem ser resolvidos por uma máquina de Turing determinística em tempo polinomial. Mais precisamente, um problema está em P se existe um algoritmo que, para qualquer entrada de tamanho n, produz a resposta correta em no máximo nᵏ passos, onde k é uma constante fixa. Esta definição captura nossa intuição de eficiência: dobrar o tamanho da entrada aumenta o tempo por um fator limitado, não exponencialmente.
Muitos problemas fundamentais da computação residem confortavelmente em P. A ordenação pode ser feita em O(n log n) com algoritmos como merge sort ou heap sort. A busca em grafos, seja em largura ou profundidade, executa em O(V + E) onde V são vértices e E são arestas. O algoritmo de Dijkstra encontra caminhos mínimos em O(E log V). Estes algoritmos formam a espinha dorsal da computação prática.
Muitos problemas que parecem requerer tempo exponencial podem ser resolvidos em tempo polinomial usando programação dinâmica. A ideia é decompor o problema em subproblemas sobrepostos, resolver cada um apenas uma vez e armazenar os resultados. O problema da mochila com pesos inteiros, sequências de Fibonacci, e alinhamento de sequências biológicas são exemplos onde esta técnica transforma complexidade exponencial aparente em polinomial.
Nem sempre precisamos examinar todas as possibilidades. Algoritmos gulosos fazem escolhas localmente ótimas esperando alcançar o ótimo global. Surpreendentemente, para muitos problemas em P, esta estratégia simples funciona perfeitamente. O algoritmo de Huffman para codificação, Dijkstra para caminhos mínimos, e Kruskal para árvores geradoras mínimas são exemplos onde a ganância compensa.
Grafos são estruturas versáteis que modelam conexões — redes sociais, mapas, circuitos, moléculas. Muitos problemas fundamentais em grafos estão em P. Determinar conectividade, encontrar componentes, detectar ciclos, calcular fluxo máximo — todos têm algoritmos polinomiais elegantes. O estudo destes algoritmos revela padrões e técnicas aplicáveis a diversos domínios.
Operações com matrizes e vetores formam a base de inúmeras aplicações, desde computação gráfica até aprendizado de máquina. Felizmente, a maioria das operações fundamentais está em P. Eliminação gaussiana resolve sistemas lineares em O(n³). Decomposições matriciais (LU, QR, SVD) têm algoritmos polinomiais eficientes. Mesmo o cálculo de determinantes e inversas, apesar de custosos, permanecem em P.
Problemas geométricos frequentemente admitem soluções elegantes em P. Calcular o envoltório convexo de pontos no plano pode ser feito em O(n log n). Detectar interseções entre segmentos, triangular polígonos, encontrar o par de pontos mais próximo — todos têm algoritmos polinomiais eficientes. A geometria computacional combina intuição visual com rigor algorítmico.
Textos e sequências são onipresentes na era digital. Buscar padrões, comparar strings, comprimir dados — problemas essenciais com soluções em P. O algoritmo KMP encontra padrões em O(n + m). Árvores de sufixo podem ser construídas em tempo linear. Mesmo problemas aparentemente complexos como encontrar a maior substring comum têm soluções polinomiais eficientes.
Uma propriedade notável de P é sua robustez. Não importa se usamos máquinas de Turing, RAM, ou computadores quânticos para problemas em P — a classe permanece a mesma (até fatores polinomiais). Esta invariância sugere que P captura algo fundamental sobre computação eficiente, independente de detalhes de implementação.
Apesar de sua riqueza, P tem limitações claras. Muitos problemas naturais e importantes parecem escapar desta classe. Fatorar números grandes, encontrar cliques máximos em grafos, resolver Sudoku de tamanho arbitrário — nenhum destes tem algoritmo polinomial conhecido. Esta observação nos leva naturalmente à próxima classe em nossa jornada: NP, onde as soluções são fáceis de verificar, mas aparentemente difíceis de encontrar.
A classe P representa o território conquistado da computação — problemas que dominamos completamente, com soluções elegantes e eficientes. É o fundamento sobre o qual construímos a tecnologia moderna, desde bancos de dados até inteligência artificial. Mas P é apenas parte da história. No próximo capítulo, exploraremos a misteriosa classe NP, onde mora uma das perguntas mais importantes da matemática: seria P igual a NP? Prepare-se para entrar em um mundo onde verificar é fácil, mas encontrar pode ser impossível!
Imagine receber um Sudoku completamente preenchido. Verificar se a solução está correta é trivial — basta checar se cada linha, coluna e quadrado contém os dígitos de 1 a 9 sem repetição. Mas encontrar essa solução do zero? Isso pode levar horas de tentativa e erro. Esta assimetria fascinante entre verificar e descobrir define a classe NP, um dos conceitos mais importantes e mal-compreendidos da ciência da computação. NP não significa "não-polinomial" como muitos pensam, mas sim "não-determinístico polinomial" — e sua compreensão é a chave para entender os limites fundamentais da computação.
A classe NP contém todos os problemas de decisão que podem ser resolvidos por uma máquina de Turing não-determinística em tempo polinomial. Mas o que significa não-determinismo? Imagine um computador mágico que, sempre que precisa fazer uma escolha, pode explorar todos os caminhos simultaneamente, como se criasse universos paralelos para cada possibilidade. Se algum desses universos encontra a resposta "sim", o problema aceita. Esta visão fantástica tem uma interpretação prática equivalente: problemas cujas soluções podem ser verificadas eficientemente.
A maneira mais intuitiva de entender NP é através de certificados. Para cada instância com resposta "sim", existe uma prova curta (polinomial no tamanho da entrada) que pode ser verificada rapidamente. Para o Sudoku, o certificado é a grade preenchida. Para o problema do caminho hamiltoniano, é a sequência de vértices. Para fatoração, são os fatores primos. O verificador não precisa ser inteligente — apenas meticuloso.
Todo problema em P também está em NP — afinal, se podemos resolver eficientemente, certamente podemos verificar eficientemente (basta resolver e comparar). Mas NP contém muito mais. A grande questão é se contém algo além de P. Esta inclusão P ⊆ NP é clara e não-controversa, mas a igualdade ou desigualdade permanece o Santo Graal da computação teórica.
NP abriga alguns dos problemas mais estudados da computação. O problema da satisfatibilidade booleana (SAT) pergunta se existe uma atribuição de verdadeiro/falso para variáveis que torna uma fórmula lógica verdadeira. O problema do caixeiro-viajante busca o tour mais curto visitando todas as cidades. O problema da coloração de grafos tenta pintar vértices com k cores sem vizinhos da mesma cor. Todos compartilham a característica: soluções difíceis de encontrar, fáceis de verificar.
Muitos jogos e quebra-cabeças populares são problemas NP disfarçados. Sudoku, palavras-cruzadas, quebra-cabeças de lógica — todos envolvem encontrar soluções que satisfazem restrições complexas. A diversão vem justamente da dificuldade de descoberta combinada com a satisfação da verificação. Esta conexão não é coincidência: nossos cérebros são atraídos por desafios na fronteira do tratável.
NP tecnicamente contém apenas problemas de decisão (resposta sim/não), mas muitos surgem de problemas de otimização. "Existe um caminho de custo menor que k?" está em NP. "Qual o caminho de menor custo?" é o problema de otimização correspondente. Se P = NP, poderíamos resolver ambos eficientemente. A versão de decisão geralmente captura a dificuldade essencial do problema de otimização.
Algoritmos randomizados às vezes resolvem problemas NP com alta probabilidade de sucesso. A classe BPP contém problemas solúveis em tempo polinomial com erro limitado. Surpreendentemente, acredita-se que BPP = P, sugerindo que aleatoriedade pode ser eliminada. Mas para NP, aleatoriedade parece menos poderosa — a classe RP (randomizada com erro unilateral) provavelmente não captura todo NP.
NP não é uma massa homogênea — tem estrutura rica e hierarquias internas. Alguns problemas são "mais difíceis" que outros no sentido de que resolvê-los eficientemente resolveria todos os outros. Estes são os problemas NP-completos, que estudaremos em detalhe no Capítulo 5. Há também problemas em NP que parecem intermediários, nem em P nem NP-completos, como fatoração e isomorfismo de grafos.
Para todo problema em NP, existe um problema complementar em co-NP onde os "sim" e "não" são trocados. Por exemplo, se "a fórmula é satisfatível?" está em NP, então "a fórmula é tautologia?" está em co-NP (tautologia = sempre verdadeira = não satisfatível quando negada). P está tanto em NP quanto em co-NP, mas não se sabe se NP = co-NP. Se forem diferentes, então P ≠ NP.
Problemas NP aparecem naturalmente em ciências. Dobramento de proteínas busca configuração tridimensional de menor energia. Inferência filogenética reconstrói árvores evolutivas. Projeto de medicamentos procura moléculas que se encaixam em receptores. A natureza parece resolver alguns destes problemas eficientemente — proteínas se dobram em milissegundos. Isso sugere P = NP? Ou a natureza usa heurísticas que funcionam na prática mas não sempre?
A classe NP captura a essência de muitos problemas importantes: aqueles onde reconhecer uma boa solução é muito mais fácil que encontrá-la. Como um detective que pode verificar rapidamente um álibi mas precisa de tempo para encontrar o culpado, NP representa o desafio da descoberta versus verificação. Esta assimetria fundamental permeia computação, matemática e ciências naturais. No próximo capítulo, confrontaremos a questão central: P é igual a NP? Esta pergunta de um milhão de dólares (literalmente!) pode revolucionar nossa compreensão da computação e do universo.
No coração da ciência da computação pulsa uma pergunta aparentemente simples que desafia as mentes mais brilhantes há meio século: P é igual a NP? Em outras palavras, se podemos verificar rapidamente uma solução, podemos também encontrá-la rapidamente? Esta questão transcende a matemática pura — sua resposta determinaria os limites fundamentais do conhecimento humano, a segurança de todas as nossas comunicações digitais, e até mesmo a natureza da criatividade e intuição. É um dos sete Problemas do Milênio, com um prêmio de um milhão de dólares aguardando quem resolver este enigma.
Se P = NP, o mundo seria radicalmente diferente. Toda vez que pudéssemos reconhecer uma solução correta, poderíamos gerá-la eficientemente. Provas matemáticas seriam automatizáveis — bastaria verificar se uma sequência de símbolos constitui uma demonstração válida. Otimização se tornaria trivial. Inteligência artificial explodiria em capacidade. Mas também, toda criptografia atual se tornaria inútil, pois decifrar mensagens seria tão fácil quanto verificar a decifragem correta.
A maioria dos especialistas acredita que P ≠ NP, embora sem prova definitiva. A intuição vem de múltiplas fontes: décadas de tentativas fracassadas de encontrar algoritmos eficientes para problemas NP-completos, a aparente necessidade de busca exaustiva em muitos casos, e a sensação filosófica de que criar é fundamentalmente mais difícil que verificar. Se P = NP, gerações de matemáticos e cientistas da computação teriam perdido algo óbvio.
A questão P vs NP emergiu gradualmente na década de 1970. Stephen Cook e Leonid Levin independentemente provaram que SAT é NP-completo em 1971, estabelecendo que resolver SAT eficientemente resolveria todos os problemas em NP. Richard Karp então mostrou que 21 problemas importantes eram NP-completos, revelando a ubiquidade do fenômeno. Desde então, milhares de problemas foram classificados, mas a questão central permanece aberta.
Por que é tão difícil provar P ≠ NP? Resultados profundos mostram que certas técnicas de prova não podem funcionar. O teorema da relativização de Baker-Gill-Solovay mostra que métodos que relativizam a oráculos não podem resolver a questão. O resultado de naturalização de Razborov-Rudich indica que provas "naturais" também falham. Estas barreiras sugerem que a prova, se existir, requererá ideias radicalmente novas.
Mesmo sem resolver P vs NP, podemos explorar as consequências de cada possibilidade. Se P = NP, existiria uma hierarquia de algoritmos cada vez mais eficientes para NP-completos. Se P ≠ NP, haveria problemas intermediários nem em P nem NP-completos (teorema de Ladner). Estudar estes mundos hipotéticos ilumina a estrutura da complexidade computacional.
Centenas de tentativas de prova foram anunciadas e refutadas. Algumas afirmam P = NP apresentando algoritmos supostamente polinomiais para NP-completos. Outras argumentam P ≠ NP através de limites inferiores. Todas falharam sob escrutínio, geralmente por erros sutis ou mal-entendidos sobre definições. O problema atrai tanto gênios quanto excêntricos, tornando a verificação de novas tentativas um processo delicado.
Já que o problema completo parece intratável, pesquisadores estudam versões restritas. P vs NP para circuitos booleanos, para computação quântica, para modelos específicos — cada variante oferece insights. Alguns resultados parciais foram obtidos: sabemos que certas técnicas de circuitos não podem resolver NP-completos, e que mundos relativizados existem onde P = NP e onde P ≠ NP.
P vs NP toca questões filosóficas profundas sobre a natureza da criatividade, intuição e descoberta. Se P = NP, não haveria diferença fundamental entre gênio criativo e verificação mecânica — Mozart seria redutível a um algoritmo. A questão também se relaciona com problemas de consciência e livre-arbítrio: somos máquinas de Turing glorificadas, ou há algo não-computável em nós?
Em 2000, o Clay Mathematics Institute designou P vs NP como um dos sete Problemas do Milênio, oferecendo $1 milhão pela solução. Os outros incluem a Hipótese de Riemann, a Conjectura de Poincaré (já resolvida), e as equações de Navier-Stokes. O prêmio reconhece não apenas a dificuldade técnica, mas a importância fundamental da questão para matemática e ciência.
Uma prova de P ≠ NP provavelmente estabeleceria um limite inferior super-polinomial para algum problema NP-completo. Precisaria evitar as barreiras conhecidas, possivelmente usando técnicas geométricas, topológicas ou de teoria dos números ainda não aplicadas à complexidade. Uma prova de P = NP forneceria um algoritmo polinomial para SAT ou outro NP-completo, revolucionando a computação.
A questão P vs NP permanece como o Everest da ciência da computação — majestosa, desafiadora, aparentemente intransponível. Cada tentativa fracassada de escalá-la nos ensina sobre os limites de nossas técnicas atuais. Cada novo ângulo revela mais da estrutura profunda da computação. Independentemente da resposta final, a jornada já transformou nossa compreensão dos limites do conhecimento. No próximo capítulo, exploraremos os problemas NP-completos — os mais difíceis em NP e a chave para entender toda a classe.
Em toda sociedade existem indivíduos cujo destino está entrelaçado com o de todos os outros — se um prospera, todos prosperam; se um sofre, todos sofrem. No reino da complexidade computacional, os problemas NP-completos desempenham esse papel central. São os problemas mais difíceis em NP, unidos por um pacto matemático: resolver qualquer um deles eficientemente significa resolver todos os problemas em NP eficientemente. Como chaves mestras computacionais, eles guardam o segredo de P versus NP. Neste capítulo, exploraremos estes problemas fascinantes, entendendo por que são equivalentes e como identificá-los na natureza.
Um problema é NP-completo se satisfaz duas condições: primeiro, está em NP (suas soluções podem ser verificadas eficientemente); segundo, é NP-difícil (todo problema em NP pode ser reduzido a ele em tempo polinomial). Esta segunda condição é crucial — significa que o problema é pelo menos tão difícil quanto qualquer outro em NP. Se encontrarmos um algoritmo polinomial para qualquer NP-completo, teremos P = NP.
O problema da satisfatibilidade booleana (SAT) foi o primeiro provado NP-completo por Cook e Levin. Dado uma fórmula booleana, existe uma atribuição de verdadeiro/falso às variáveis que a torna verdadeira? A prova genial mostra que qualquer computação não-determinística polinomial pode ser codificada como uma fórmula SAT. Este resultado fundamental estabeleceu a NP-completude como conceito central.
Um dos NP-completos mais famosos e estudados, o problema do caixeiro-viajante (TSP) busca o tour mais curto visitando todas as cidades exatamente uma vez. Apesar de sua formulação simples, captura a essência de problemas de otimização combinatória. Aplicações vão desde roteamento de veículos até fabricação de chips, onde um laser deve perfurar milhares de pontos minimizando movimento.
Dado um grafo e k cores, podemos colorir os vértices de modo que vizinhos tenham cores diferentes? Este problema modela alocação de recursos com conflitos — frequências de rádio, horários de exames, registradores em compiladores. Para k ≥ 3, o problema é NP-completo. A versão com k = 2 está em P (basta verificar se o grafo é bipartido).
O problema do clique busca o maior subgrafo completo — um conjunto de vértices todos conectados entre si. Modela comunidades coesas em redes sociais, proteínas interagentes em biologia, palavras relacionadas em linguística. Seu dual, conjunto independente, busca vértices sem conexões mútuas. Ambos são NP-completos e fundamentais em teoria dos grafos.
Um ladrão tem uma mochila com capacidade limitada e deve escolher quais itens roubar maximizando valor total. Este problema de otimização aparece em investimentos (portfólio com orçamento limitado), criptografia (construção de somas de subconjuntos), e corte de materiais (minimizar desperdício). A versão de decisão ("existe seleção com valor ≥ V?") é NP-completa.
Encontrar o menor conjunto de vértices que "toca" todas as arestas do grafo. Essencial em design de redes onde queremos monitorar todas as conexões com o mínimo de sensores. Também modela problemas de vigilância, onde guardas em vértices observam arestas adjacentes. Intimamente relacionado com conjunto independente — o complemento de uma cobertura mínima é um conjunto independente máximo.
Dado um conjunto de números, existe um subconjunto que soma exatamente um valor alvo? Este problema aparentemente simples é NP-completo e fundamental em criptografia. A variante de partição pergunta se podemos dividir números em dois grupos de soma igual — relevante em balanceamento de carga e divisão justa de recursos.
Existe um caminho visitando cada vértice exatamente uma vez? Este problema é primo do TSP mas sem considerar distâncias — apenas conectividade importa. Aplicações incluem genômica (montagem de DNA), torneios (todos jogam contra todos), e até solução de puzzles como o cavalo no xadrez visitando todas as casas.
NP-completos formam uma rede densa de reduções — cada um pode ser transformado em qualquer outro polinomialmente. Esta inter-conectividade é notável: problemas de lógica, grafos, números, geometria — todos equivalentes computacionalmente. Dominar uma redução clássica como SAT→3-SAT→CLIQUE→VERTEX-COVER é rito de passagem em complexidade.
Os problemas NP-completos são os guardiões do mistério P versus NP. Como uma sociedade secreta matemática, eles protegem coletivamente o segredo — quebrar um é quebrar todos. Sua onipresença em ciência e engenharia torna a questão P vs NP não apenas teórica, mas prática e urgente. No próximo capítulo, exploraremos a arte das reduções — a técnica fundamental para provar NP-completude e entender as conexões profundas entre problemas aparentemente distintos.
Na matemática, como na vida, problemas aparentemente distintos frequentemente escondem conexões profundas. A técnica de redução revela estas conexões, mostrando como transformar um problema em outro. É como descobrir que saber cozinhar massa permite fazer tanto espaguete quanto lasanha — dominar o fundamental resolve múltiplas questões. Em complexidade computacional, reduções são a ferramenta principal para classificar problemas, provar NP-completude, e entender a estrutura do universo computacional. Neste capítulo, dominaremos esta arte transformativa, aprendendo a construir pontes entre problemas e provar equivalências computacionais.
Reduzir problema A ao problema B significa criar um método eficiente para resolver A usando uma solução para B como sub-rotina. Se A reduz a B, então B é pelo menos tão difícil quanto A — afinal, resolver B nos dá automaticamente uma solução para A. Esta relação "pelo menos tão difícil quanto" ordena problemas por dificuldade computacional, criando uma hierarquia de complexidade.
Existem várias noções de redução, cada uma capturando diferentes aspectos de relacionamento entre problemas. Reduções de Karp (many-one) transformam instâncias preservando respostas. Reduções de Cook (Turing) permitem múltiplas consultas ao oráculo. Reduções de espaço logarítmico são ainda mais restritivas. A escolha depende do contexto e do que queremos provar.
Para provar que um problema X é NP-completo, seguimos uma receita estabelecida: primeiro, mostrar que X está em NP (geralmente fácil — exibir verificador polinomial); segundo, escolher um problema Y já conhecido NP-completo; terceiro, construir redução de Y para X. A parte desafiadora é a construção criativa de gadgets que codifiquem Y em termos de X.
Uma das reduções mais elegantes transforma SAT geral em 3-SAT (cláusulas com exatamente 3 literais). Para cláusulas com mais de 3 literais, introduzimos variáveis auxiliares que forçam satisfatibilidade equivalente. Por exemplo, (a ∨ b ∨ c ∨ d) torna-se (a ∨ b ∨ z) ∧ (¬z ∨ c ∨ d) com nova variável z. Esta técnica ilustra como restrições estruturais podem ser simuladas.
A redução de 3-SAT para CLIQUE é uma obra-prima de engenharia. Para cada cláusula, criamos um triângulo de vértices representando os três literais. Conectamos vértices de triângulos diferentes exceto quando representam literal e sua negação. Um clique de tamanho k (número de cláusulas) corresponde a uma atribuição satisfazendo a fórmula. A construção visual torna a equivalência quase óbvia.
Gadgets são pequenas estruturas que simulam componentes lógicos ou computacionais. Na redução de 3-SAT para HAMILTONIAN PATH, construímos gadgets representando variáveis (caminhos com escolha de direção) e cláusulas (desvios verificando satisfação). A arte está em garantir que caminhos hamiltonianos correspondam exatamente a atribuições satisfazendo a fórmula.
O conceito de completude não se limita a NP. Existem problemas P-completos (os mais difíceis em P para paralelização), PSPACE-completos (jogos como Go generalizado), EXPTIME-completos (xadrez generalizado). Cada classe tem seus representantes mais difíceis, identificados através de reduções apropriadas.
Quando problemas de otimização são NP-difíceis, buscamos aproximações. Reduções que preservam aproximação (AP-reduções) mostram que aproximar um problema é tão difícil quanto aproximar outro. Por exemplo, aproximar CLIQUE MÁXIMO dentro de fator constante é tão difícil quanto aproximar CONJUNTO INDEPENDENTE MÁXIMO.
Segurança criptográfica baseia-se em reduções mostrando que quebrar um sistema é tão difícil quanto resolver problemas presumivelmente intratáveis. RSA reduz-se a fatoração, sistemas baseados em curvas elípticas a logaritmo discreto. Estas reduções garantem que atacar o sistema requer resolver problemas estudados há décadas sem sucesso.
Construir reduções elegantes é arte e ciência. Requer criatividade para ver conexões não-óbvias, técnica para construir transformações corretas, e rigor para provar preservação de propriedades. Grandes reduções revelam estruturas profundas — como a redução de Cook mostrando universalidade de SAT, ou reduções PCP revolucionando teoria de aproximação.
Reduções são as pontes do mundo computacional, conectando problemas aparentemente distintos em uma teia de equivalências. Dominar esta técnica permite navegar o universo da complexidade com confiança, classificando novos problemas e entendendo suas relações com questões clássicas. Como cartógrafos mapeando território desconhecido, usamos reduções para expandir constantemente nossa compreensão dos limites da computação. No próximo capítulo, exploraremos como enfrentar problemas NP-completos na prática através de algoritmos aproximados e heurísticas.
O mundo real não espera pela resolução de P versus NP. Empresas precisam roteirizar entregas, fábricas devem sequenciar produção, redes requerem otimização — todos problemas NP-difíceis que demandam soluções hoje, não em um futuro teórico distante. Como navegadores enfrentando mares tempestuosos sem mapa perfeito, desenvolvemos técnicas para encontrar soluções boas o suficiente, rápido o suficiente. Neste capítulo, exploraremos o arsenal de ferramentas práticas para atacar problemas intratáveis: algoritmos de aproximação com garantias, heurísticas espertas sem garantias, e meta-heurísticas que imitam processos naturais.
Um algoritmo de aproximação garante solução dentro de fator multiplicativo do ótimo. Para problema de minimização, se garante custo no máximo α vezes o ótimo, temos α-aproximação. O algoritmo guloso para cobertura de vértices sempre encontra solução com no máximo o dobro de vértices necessários — uma 2-aproximação simples mas poderosa. Estas garantias importam: sabemos quão longe do ideal podemos estar.
Alguns problemas admitem esquemas de aproximação polinomial (PTAS) — para qualquer ε > 0, existe algoritmo (1+ε)-aproximação. O tempo pode ser exponencial em 1/ε, mas polinomial no tamanho da entrada. Melhor ainda são FPTAS (fully polynomial-time approximation schemes), polinomiais também em 1/ε. O problema da mochila tem FPTAS via programação dinâmica com arredondamento.
Algoritmos gulosos fazem escolhas localmente ótimas esperando bom resultado global. Sem garantias teóricas, frequentemente funcionam espetacularmente na prática. Para TSP, "nearest neighbor" visita sempre a cidade mais próxima não visitada. Simples, rápido, e muitas vezes produz tours apenas 15-20% piores que o ótimo em instâncias reais.
Começando com solução qualquer, busca local repetidamente move para vizinho melhor até alcançar ótimo local. Para TSP, 2-opt troca pares de arestas melhorando o tour. 3-opt considera triplas. Lin-Kernighan generaliza com trocas complexas. Ótimos locais podem ser distantes do global, mas iteração e perturbação ajudam escapar de armadilhas.
Inspirados na evolução biológica, algoritmos genéticos mantêm população de soluções que se reproduzem, mutam e competem. Crossover combina características de pais promissores. Mutação introduz diversidade. Seleção favorece mais aptos. Após gerações, soluções excelentes emergem. Funcionam bem para problemas com estrutura que crossover pode explorar.
Imitando o resfriamento de metais, simulated annealing aceita movimentos ruins com probabilidade decrescente ao longo do tempo. Inicialmente, "temperatura" alta permite exploração ampla. Gradualmente resfriando, o algoritmo se concentra em refinamento local. A analogia física sugere parâmetros e garante convergência probabilística ao ótimo global com resfriamento suficientemente lento.
Formigas encontram caminhos curtos depositando feromônio que atrai outras formigas. Algoritmos ACO (Ant Colony Optimization) simulam este processo: formigas artificiais constroem soluções probabilisticamente, boas soluções recebem mais feromônio, feromônio evapora prevenindo convergência prematura. Excelente para problemas de roteamento e sequenciamento.
Para garantir otimalidade quando possível, branch and bound explora árvore de decisões podando ramos provadamente sub-ótimos. Bounds (limites) inferiores e superiores guiam a poda. Funciona bem quando bounds são apertados e ótimo não está profundo na árvore. Combina garantia de otimalidade com eficiência prática em muitas instâncias.
Muitos problemas combinatórios podem ser formulados como programas inteiros. Relaxando integralidade, obtemos programa linear solúvel em tempo polinomial. A solução fracionária fornece bound e às vezes sugere boa solução inteira via arredondamento. Para vertex cover, a relaxação LP dá 2-aproximação. Técnicas sofisticadas como cutting planes melhoram bounds iterativamente.
Recentemente, ML tem revolucionado design de heurísticas. Redes neurais aprendem a construir soluções, prever variáveis promissoras, ou guiar busca. Reinforcement learning treina políticas para decisões sequenciais. Graph neural networks capturam estrutura de problemas em grafos. Aprendizado transfere entre instâncias similares, amortizando custo de treino.
Enfrentar problemas NP-completos na prática é uma dança entre teoria e pragmatismo. Algoritmos de aproximação oferecem garantias reconfortantes. Heurísticas sacrificam garantias por eficiência. Meta-heurísticas exploram analogias naturais em busca de soluções. A escolha depende do contexto: precisamos de garantias? Qual o tamanho típico? Quanto tempo temos? A arte está em combinar técnicas, explorar estrutura específica do problema, e aceitar que "bom o suficiente" frequentemente é perfeito para o mundo real. No próximo capítulo, veremos estas técnicas em ação resolvendo problemas práticos que impactam bilhões diariamente.
Enquanto teóricos debatem P versus NP em torres de marfim, engenheiros e cientistas enfrentam problemas NP-completos diariamente no front de batalha da tecnologia. Cada vez que você recebe uma encomenda, usa GPS, joga um game complexo ou faz uma busca na web, algoritmos estão nos bastidores domando problemas teoricamente intratáveis. A diferença entre teoria e prática é que, na prática, nem sempre precisamos da solução perfeita — apenas uma suficientemente boa, suficientemente rápida. Neste capítulo, exploraremos como conceitos abstratos de complexidade se materializam em aplicações que movem o mundo moderno.
Gigantes como Amazon, FedEx e UPS enfrentam versões massivas do problema do caixeiro-viajante diariamente. Com milhões de pacotes, milhares de veículos e restrições de tempo, encontrar rotas ótimas é computacionalmente impossível. Mas heurísticas sofisticadas, combinando busca local, algoritmos genéticos e machine learning, produzem rotas apenas 3-5% piores que o ótimo teórico, economizando bilhões em combustível e tempo.
Projetar e otimizar redes de telecomunicações envolve múltiplos problemas NP-completos. Onde colocar torres de celular (cobertura de conjuntos)? Como rotear dados minimizando latência (caminhos disjuntos)? Como alocar frequências evitando interferência (coloração de grafos)? Operadoras usam aproximações e heurísticas para gerenciar redes servindo bilhões de dispositivos em tempo real.
A biologia molecular está repleta de problemas NP-difíceis. Prever como proteínas se dobram em estruturas tridimensionais, alinhar múltiplas sequências de DNA, reconstruir árvores evolutivas — todos desafiam computação exata. Mas aproximações e heurísticas, especialmente com recent es avanços em deep learning como AlphaFold, têm revolucionado nossa capacidade de entender e manipular sistemas biológicos.
Mercados financeiros são campos de batalha de otimização. Construir portfólios balanceando risco e retorno, executar grandes ordens minimizando impacto no mercado, detectar padrões em dados de alta frequência — todos envolvem problemas computacionalmente difíceis. Fundos quantitativos empregam exércitos de Ph.Ds desenvolvendo algoritmos que ganham ou perdem milhões em microssegundos.
Fábricas modernas são sinfonias de otimização. Sequenciar tarefas em máquinas (job shop scheduling), cortar materiais minimizando desperdício (bin packing), alocar recursos limitados — problemas NP-difíceis por toda parte. Indústria 4.0 usa IoT e IA para otimização em tempo real, com algoritmos adaptativos respondendo a mudanças instantaneamente.
Videogames modernos resolvem problemas NP-completos em tempo real. Pathfinding para centenas de unidades (A* com heurísticas), geração procedural de mundos (satisfazendo restrições complexas), balanceamento de gameplay (otimização multi-objetivo) — tudo deve rodar a 60 frames por segundo. Desenvolvedores são mestres em aproximações que parecem perfeitas ao jogador.
Treinar redes neurais profundas é, em geral, NP-difícil. Encontrar pesos ótimos, selecionar features, ajustar hiperparâmetros — todos intratáveis em teoria. Mas gradiente descendente e variantes, apesar de garantirem apenas ótimos locais, funcionam espetacularmente na prática. O sucesso do deep learning desafia nossa compreensão teórica, sugerindo que problemas práticos têm estrutura que algoritmos podem explorar.
Cidades são sistemas complexos requirindo otimização constante. Onde construir hospitais para maximizar acesso (facility location)? Como sincronizar semáforos para fluxo ótimo? Como planejar rotas de transporte público? Urbanistas usam simulações e otimização para decisões impactando milhões de vidas.
A transição energética global depende de resolver problemas de otimização massivos. Como integrar fontes renováveis intermitentes na rede elétrica? Onde instalar painéis solares e turbinas eólicas? Como balancear oferta e demanda em tempo real? Smart grids usam algoritmos sofisticados para gerenciar complexidade crescente do sistema energético moderno.
Fazendas modernas são fábricas ao ar livre otimizando cada decisão. Quando plantar para maximizar yield considerando previsões climáticas? Como rotear tratores minimizando combustível? Onde aplicar fertilizantes com precisão? Drones, sensores e IA transformam agricultura em problema de otimização computacional, aumentando produtividade enquanto reduz impacto ambiental.
A onipresença de problemas NP-completos no mundo real é tanto desafio quanto oportunidade. Desafio porque soluções perfeitas são impossíveis para instâncias grandes. Oportunidade porque pequenas melhorias em algoritmos podem gerar bilhões em valor. A lacuna entre teoria (exponencial) e prática (soluções boas rapidamente) sugere que problemas reais têm estrutura especial que podemos explorar. Talvez P ≠ NP no pior caso, mas instâncias práticas vivem em ilhas de tratabilidade no oceano da complexidade. No próximo capítulo, veremos como a dureza computacional, longe de ser apenas obstáculo, tornou-se fundação da segurança digital moderna.
Em um paradoxo fascinante, a mesma dureza computacional que frustra cientistas tentando resolver problemas NP-completos protege bilhões de transações digitais diariamente. A criptografia moderna transformou a maldição da intratabilidade em bênção, construindo fortalezas matemáticas onde a segurança deriva precisamente da dificuldade computacional de certos problemas. Cada vez que você faz uma compra online, acessa sua conta bancária ou envia uma mensagem privada, está confiando na hipótese de que certos problemas matemáticos são genuinamente difíceis. Neste capítulo, exploraremos como complexidade computacional se tornou o guardião da privacidade e segurança na era digital.
O conceito fundamental da criptografia moderna é a função de mão única: fácil de computar em uma direção, mas computacionalmente impossível de inverter. Multiplicar dois primos de 300 dígitos leva microssegundos; fatorar o produto pode levar mais que a idade do universo. Esta assimetria dramática entre fazer e desfazer é a pedra angular sobre a qual construímos segurança digital.
O sistema RSA, nomeado após Rivest, Shamir e Adleman, revolucionou comunicação segura. Sua segurança repousa na dificuldade de fatorar produtos de primos grandes. Com chaves de 2048 bits, mesmo todos os computadores do mundo trabalhando juntos levariam eras para quebrar uma única mensagem. Mas se alguém descobrir algoritmo eficiente para fatoração, RSA desmorona instantaneamente.
Surpreendentemente, P ≠ NP não é suficiente para garantir segurança criptográfica. Mesmo se P ≠ NP, poderia existir algoritmo que quebra criptografia em tempo n^100 — polinomial mas impraticável. Ou pior, algoritmos polinomiais para problemas médios enquanto apenas o pior caso é exponencial. Criptografia precisa de dureza mais forte: problemas difíceis em média para instâncias escolhidas aleatoriamente.
Um dos desenvolvimentos mais extraordinários em criptografia são as provas de conhecimento zero: convencer alguém de que você sabe algo sem revelar o que sabe. Imagine provar que conhece a solução de um Sudoku sem mostrar nenhum número! Surpreendentemente, se funções de mão única existem, todo problema em NP tem prova de conhecimento zero, conectando profundamente complexidade e criptografia.
Computadores quânticos ameaçam destruir criptografia atual — algoritmo de Shor fatora eficientemente, quebrando RSA. Mas nem tudo está perdido. Certos problemas parecem difíceis mesmo para computadores quânticos: lattice problems, códigos de correção de erro, polinômios multivariados, hashes. A corrida está em padronizar novos sistemas antes que computadores quânticos grandes existam.
Bitcoin transformou dureza computacional em consenso distribuído. Mineradores competem para resolver puzzles criptográficos (encontrar nonce produzindo hash com zeros iniciais), com dificuldade ajustada para manter tempo médio de 10 minutos por bloco. Este "proof of work" desperdiça energia deliberadamente, tornando ataques proibitivamente caros. A segurança emerge da termodinâmica!
O Santo Graal da criptografia é ofuscação de programas: transformar código em versão incompreensível mas funcionalmente equivalente. Com ofuscação perfeita, poderíamos distribuir software sem revelar algoritmos proprietários. Infelizmente, ofuscação de "caixa preta" é impossível em geral, mas versões mais fracas como ofuscação indistinguível mostram promessa para casos específicos.
Como múltiplas partes podem computar função conjunta de seus inputs privados sem revelar os inputs? Por exemplo, calcular salário médio sem ninguém revelar seu salário individual. MPC (Multiparty Computation) resolve este problema usando técnicas como secret sharing e garbled circuits. Aplicações vão de leilões sealed-bid a análise de dados médicos preservando privacidade.
Criptografia depende crucialmente de aleatoriedade verdadeira. Mas computadores são determinísticos! Geradores pseudoaleatórios (PRGs) expandem sementes curtas verdadeiramente aleatórias em sequências longas computacionalmente indistinguíveis de aleatórias. A segurança de PRGs reduz-se a dureza computacional — se PRGs seguros existem, então P ≠ NP.
À medida que computadores clássicos se aproximam de limites físicos e computadores quânticos emergem, a criptografia evolui. Fully homomorphic encryption permite computação em dados encriptados. Functional encryption dá acesso controlado a funções dos dados. Witness encryption condiciona decriptação em provas. Cada avanço entrelaça mais profundamente complexidade e criptografia.
A criptografia moderna é um milagre da complexidade computacional aplicada. Transformamos a frustração de não poder resolver certos problemas eficientemente na garantia de que adversários também não podem. Cada transação segura, cada senha protegida, cada comunicação privada depende da aposta de que P ≠ NP ou pelo menos que certos problemas específicos são genuinamente difíceis. É uma aposta que fazemos trilhões de vezes por dia, e até agora, tem valido a pena. No capítulo final, exploraremos as fronteiras da computação — o que está além de P e NP, e o que o futuro reserva para complexidade computacional.
Para além das classes P e NP existe um universo vasto e inexplorado de complexidade computacional. Como antigos cartógrafos marcando "aqui há dragões" em territórios desconhecidos, teóricos da computação mapeiam regiões cada vez mais exóticas: problemas que requerem toda a memória do universo, computações que transcendem a física clássica, questões que desafiam a própria noção de algoritmo. Neste capítulo final, viajaremos às fronteiras do conhecimento computacional, explorando o que sabemos, o que suspeitamos, e o que permanece envolto em mistério sobre os limites últimos da computação.
Se NP captura problemas com certificados verificáveis, o que captura problemas com certificados de certificados? A hierarquia polinomial (PH) estende NP em níveis infinitos de quantificação alternada. Σ₂ contém problemas da forma "existe x tal que para todo y, P(x,y)", enquanto Π₂ inverte os quantificadores. Cada nível captura complexidade adicional, e o colapso da hierarquia teria consequências profundas.
Quando permitimos espaço polinomial mas tempo potencialmente exponencial, chegamos a PSPACE. Esta classe captura jogos complexos como Go generalizado, xadrez em tabuleiros n×n, e planejamento com incerteza. Surpreendentemente, PSPACE = APSPACE — adicionar não-determinismo não aumenta o poder quando temos espaço polinomial, ao contrário do que suspeitamos para tempo.
Computadores quânticos exploram superposição e entrelaçamento para processar informação de formas impossíveis classicamente. BQP (Bounded-error Quantum Polynomial time) contém problemas solúveis eficientemente com computadores quânticos. Fatoração está em BQP (algoritmo de Shor) mas não conhecidamente em P. Porém, BQP parece incomparável com NP — nem contém nem está contido.
Às vezes não queremos apenas saber se existe solução, mas quantas existem. #P captura problemas de contagem, como número de atribuições satisfazendo fórmula SAT. Surpreendentemente, #P contém problemas mais difíceis que NP — contar soluções parece fundamentalmente mais difícil que encontrar uma. O permanente de matrizes, crucial em física estatística, é #P-completo.
Quando computação é distribuída, comunicação se torna o gargalo. Alice tem x, Bob tem y, e querem computar f(x,y) minimizando bits trocados. Esta abstração modela protocolos de rede, computação distribuída, e até circuitos VLSI. Separações exponenciais existem entre protocolos determinísticos, randomizados e quânticos.
Provas interativas generalizam NP permitindo interação entre provador poderoso e verificador eficiente. IP (Interactive Polynomial time) surpreendentemente equals PSPACE — interação com aleatoriedade dá poder tremendo. Ainda mais surpreendente: MIP (Multiple provers) = NEXP, e com provers entrelaçados quanticamente, MIP* = RE (recursively enumerable), conectando computação com física fundamental.
Provar que problemas são difíceis é notoriamente difícil. Sabemos que existem funções requerendo circuitos de tamanho exponencial (argumento de contagem), mas exibir uma explícita permanece aberto. Barreiras como naturalização e algebrização explicam por que técnicas atuais falham. Novos métodos, possivelmente de geometria algébrica ou teoria dos números, podem ser necessários.
E se permitirmos "dicas" dependendo apenas do tamanho da entrada? P/poly contém problemas solúveis com circuitos de tamanho polinomial — equivalentemente, tempo polinomial com conselho polinomial. Surpreendentemente, P/poly contém problemas indecidíveis! BPP ⊆ P/poly sugere que aleatoriedade pode ser eliminada com conselhos adequados.
A complexidade de Kolmogorov mede o tamanho do menor programa gerando uma string. Strings aleatórias têm alta complexidade (incompressíveis), enquanto strings estruturadas têm baixa. Infelizmente, complexidade de Kolmogorov é incomputável — não existe algoritmo determinando o menor programa. Esta incomputabilidade tem conexões profundas com teoremas de incompletude de Gödel.
A complexidade computacional está em uma encruzilhada excitante. Computação quântica promete novos algoritmos e complexidades. Machine learning desafia noções tradicionais de tratabilidade. Computação biológica e neuromórfica sugere novos modelos. Proof assistants verificam provas cada vez mais complexas. O futuro promete não apenas resolver P vs NP, mas revelar estruturas ainda mais profundas no tecido da computação.
As fronteiras da computação se expandem constantemente, revelando paisagens cada vez mais ricas e surpreendentes. De P e NP às profundezas de MIP* e complexidade de Kolmogorov, cada descoberta levanta novas questões. Talvez a lição mais profunda seja que computação não é apenas sobre máquinas e algoritmos, mas sobre a própria natureza da informação, conhecimento e realidade. As classes P e NP, que começaram como questões técnicas sobre eficiência, revelaram-se como janelas para questões fundamentais sobre o que pode ser conhecido, provado e computado no universo. A jornada continua, e as maiores descobertas certamente ainda estão por vir.
Este volume sobre Classes P e NP foi construído sobre décadas de pesquisa em complexidade computacional, desde os trabalhos pioneiros de Cook, Karp e Levin até desenvolvimentos contemporâneos em computação quântica e criptografia. Esta bibliografia oferece recursos para aprofundamento, abrangendo tanto fundamentos teóricos quanto aplicações práticas, adequados para estudantes do ensino médio interessados em matemática e computação avançadas.
AARONSON, Scott. Quantum Computing Since Democritus. Cambridge: Cambridge University Press, 2013.
ARORA, Sanjeev; BARAK, Boaz. Computational Complexity: A Modern Approach. Cambridge: Cambridge University Press, 2009.
BRASIL. Base Nacional Comum Curricular: Educação é a Base. Brasília: MEC/CONSED/UNDIME, 2018.
COOK, Stephen A. The Complexity of Theorem-Proving Procedures. Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, p. 151-158, 1971.
CORMEN, Thomas H. et al. Algoritmos: Teoria e Prática. 3ª ed. Rio de Janeiro: Elsevier, 2012.
DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algoritmos. São Paulo: McGraw-Hill, 2009.
DOWNEY, Rod; FELLOWS, Michael. Parameterized Complexity. New York: Springer, 1999.
EDMONDS, Jack. Paths, Trees, and Flowers. Canadian Journal of Mathematics, v. 17, p. 449-467, 1965.
FORTNOW, Lance. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton: Princeton University Press, 2013.
GAREY, Michael R.; JOHNSON, David S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1979.
GOLDREICH, Oded. Computational Complexity: A Conceptual Perspective. Cambridge: Cambridge University Press, 2008.
GOLDREICH, Oded. P, NP, and NP-Completeness: The Basics of Computational Complexity. Cambridge: Cambridge University Press, 2010.
HARTMANIS, Juris; STEARNS, Richard E. On the Computational Complexity of Algorithms. Transactions of the American Mathematical Society, v. 117, p. 285-306, 1965.
HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introdução à Teoria de Autômatos, Linguagens e Computação. Rio de Janeiro: Elsevier, 2003.
IMPAGLIAZZO, Russell. A Personal View of Average-Case Complexity. Proceedings of the 10th Annual Structure in Complexity Theory Conference, p. 134-147, 1995.
KARP, Richard M. Reducibility Among Combinatorial Problems. In: Complexity of Computer Computations. New York: Plenum Press, p. 85-103, 1972.
KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. Boston: Addison-Wesley, 2006.
KNUTH, Donald E. The Art of Computer Programming. 3rd ed. Boston: Addison-Wesley, 1997-2011. 4 v.
LADNER, Richard E. On the Structure of Polynomial Time Reducibility. Journal of the ACM, v. 22, n. 1, p. 155-171, 1975.
LEVIN, Leonid A. Universal Sequential Search Problems. Problems of Information Transmission, v. 9, n. 3, p. 265-266, 1973.
LI, Ming; VITÁNYI, Paul. An Introduction to Kolmogorov Complexity and Its Applications. 3rd ed. New York: Springer, 2008.
MENEZES, Alfred J.; VAN OORSCHOT, Paul C.; VANSTONE, Scott A. Handbook of Applied Cryptography. Boca Raton: CRC Press, 1996.
MOORE, Cristopher; MERTENS, Stephan. The Nature of Computation. Oxford: Oxford University Press, 2011.
MOTWANI, Rajeev; RAGHAVAN, Prabhakar. Randomized Algorithms. Cambridge: Cambridge University Press, 1995.
NIELSEN, Michael A.; CHUANG, Isaac L. Computação Quântica e Informação Quântica. Porto Alegre: Bookman, 2005.
PAPADIMITRIOU, Christos H. Computational Complexity. Reading: Addison-Wesley, 1994.
RAZBOROV, Alexander A.; RUDICH, Steven. Natural Proofs. Journal of Computer and System Sciences, v. 55, n. 1, p. 24-35, 1997.
RIVEST, Ronald L.; SHAMIR, Adi; ADLEMAN, Leonard. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, v. 21, n. 2, p. 120-126, 1978.
RUSSELL, Stuart; NORVIG, Peter. Inteligência Artificial. 3ª ed. Rio de Janeiro: Elsevier, 2013.
SAVITCH, Walter J. Relationships Between Nondeterministic and Deterministic Tape Complexities. Journal of Computer and System Sciences, v. 4, n. 2, p. 177-192, 1970.
SCHÖNING, Uwe; PRUIM, Randall. Gems of Theoretical Computer Science. Berlin: Springer, 1998.
SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4th ed. Boston: Addison-Wesley, 2011.
SHOR, Peter W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, v. 26, n. 5, p. 1484-1509, 1997.
SIPSER, Michael. Introdução à Teoria da Computação. 2ª ed. São Paulo: Cengage Learning, 2007.
STOCKMEYER, Larry J.; MEYER, Albert R. Word Problems Requiring Exponential Time. Proceedings of the 5th Annual ACM Symposium on Theory of Computing, p. 1-9, 1973.
TODA, Seinosuke. PP is as Hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing, v. 20, n. 5, p. 865-877, 1991.
TURING, Alan M. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, v. 42, n. 2, p. 230-265, 1936.
VALIANT, Leslie G. The Complexity of Computing the Permanent. Theoretical Computer Science, v. 8, n. 2, p. 189-201, 1979.
VAZIRANI, Vijay V. Approximation Algorithms. Berlin: Springer, 2001.
WEGENER, Ingo. Complexity Theory: Exploring the Limits of Efficient Algorithms. Berlin: Springer, 2005.
WIGDERSON, Avi. Mathematics and Computation: A Theory Revolutionizing Technology and Science. Princeton: Princeton University Press, 2019.
WILLIAMSON, David P.; SHMOYS, David B. The Design of Approximation Algorithms. Cambridge: Cambridge University Press, 2011.
WOEGINGER, Gerhard J. A Compendium of NP Optimization Problems. Disponível online, atualizado regularmente, 2003-presente.
YAO, Andrew Chi-Chih. Some Complexity Questions Related to Distributive Computing. Proceedings of the 11th Annual ACM Symposium on Theory of Computing, p. 209-213, 1979.
ZIVIANI, Nivio. Projeto de Algoritmos com Implementações em Pascal e C. 3ª ed. São Paulo: Cengage Learning, 2010.