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 que você precisa organizar uma festa para sua turma. Convidar pessoas é fácil — basta enviar mensagens uma por uma. Mas e se você quiser formar grupos de trabalho onde todos se dão bem entre si? De repente, o problema explode em complexidade. Este salto dramático da simplicidade para a dificuldade computacional é o coração pulsante da teoria da NP-completude, um dos mistérios mais fascinantes e práticos da matemática moderna. Nesta jornada, descobriremos por que alguns problemas parecem impossíveis de resolver rapidamente, mesmo com os computadores mais poderosos do mundo.
Nossa era digital funciona graças aos algoritmos — receitas precisas que dizem aos computadores como resolver problemas. Alguns algoritmos são incrivelmente rápidos: ordenar mil números leva frações de segundo. Outros parecem desesperadoramente lentos: encontrar o menor caminho visitando todas as cidades do Brasil pode levar mais tempo que a idade do universo. Esta diferença brutal entre problemas "fáceis" e "difíceis" moldou toda a ciência da computação.
Nos anos 1970, cientistas da computação perceberam algo extraordinário: centenas de problemas aparentemente diferentes compartilhavam uma característica misteriosa. Todos pareciam igualmente difíceis, e resolver qualquer um deles rapidamente resolveria todos os outros. Stephen Cook e Leonid Levin, trabalhando independentemente, formalizaram esta descoberta, criando a teoria da NP-completude que revolucionaria nossa compreensão sobre computação.
Em computação, tempo não se mede em segundos, mas em operações. Um algoritmo que precisa de n² operações para processar n elementos é considerado eficiente. Já um que precisa de 2ⁿ operações torna-se rapidamente impraticável: para apenas 100 elementos, precisaríamos de mais operações que átomos no universo observável. Esta explosão exponencial é o pesadelo computacional que define os problemas NP-completos.
Para estudar rigorosamente a complexidade, precisamos de um modelo matemático de computação. A máquina de Turing, inventada por Alan Turing em 1936, é surpreendentemente simples: uma fita infinita, um cabeçote que lê e escreve símbolos, e um conjunto de regras. Apesar da simplicidade, ela captura a essência de qualquer computação possível. Todo smartphone, supercomputador ou computador quântico não pode fazer nada que uma máquina de Turing não possa — apenas mais rápido.
Uma máquina de Turing comum é determinística: em cada passo, sabe exatamente o que fazer. Uma máquina não-determinística é como ter infinitos assistentes mágicos: pode explorar todos os caminhos possíveis simultaneamente e escolher o melhor instantaneamente. Obviamente, tais máquinas não existem fisicamente, mas são cruciais para entender a classe NP — problemas que máquinas não-determinísticas resolveriam rapidamente.
Problemas computacionais formam uma hierarquia baseada em recursos necessários. A classe P contém problemas com algoritmos polinomiais — considerados "tratáveis". A classe NP contém problemas cujas soluções podem ser verificadas rapidamente. EXPTIME contém problemas que precisam de tempo exponencial. Surpreendentemente, não sabemos se P = NP, apesar de décadas de pesquisa intensa.
A beleza da classe NP está na verificação. Considere um quebra-cabeça sudoku: encontrar a solução pode ser difícil, mas verificar se uma grade preenchida está correta é trivial. Esta assimetria entre resolver e verificar define NP. Se alguém lhe der um certificado (solução proposta), você pode conferir rapidamente se está correto. É como a diferença entre compor uma sinfonia e reconhecer se ela soa harmoniosa.
A questão "P = NP?" pergunta se todo problema cuja solução pode ser verificada rapidamente também pode ser resolvida rapidamente. Se P = NP, o mundo mudaria drasticamente: criptografia moderna colapsaria, otimização se tornaria trivial, descobertas científicas seriam automatizadas. A maioria dos especialistas acredita que P ≠ NP, mas ninguém conseguiu provar. O Clay Mathematics Institute oferece um milhão de dólares pela resposta.
Provar P ≠ NP requer mostrar que nenhum algoritmo eficiente existe para problemas NP-completos — uma afirmação sobre todos os algoritmos possíveis, incluindo aqueles ainda não imaginados. É como provar que nenhuma estratégia pode garantir vitória na loteria. Técnicas tradicionais de matemática parecem inadequadas, sugerindo que precisamos de insights revolucionários ainda não descobertos.
Este capítulo estabeleceu os alicerces para nossa exploração da NP-completude. Vimos como problemas computacionais variam drasticamente em dificuldade, conhecemos a máquina de Turing como modelo fundamental, e encontramos o mistério central P versus NP. Como arqueólogos preparando uma escavação, reunimos as ferramentas necessárias para desenterrar os tesouros da teoria da complexidade.
Nos próximos capítulos, mergulharemos mais fundo neste universo fascinante. Exploraremos as classes P e NP em detalhes, aprenderemos a técnica poderosa de redução polinomial, e descobriremos o teorema revolucionário de Cook-Levin. Prepare-se para uma viagem intelectual que mudará sua forma de pensar sobre computação, problemas e os limites fundamentais do que podemos calcular eficientemente!
No universo da computação, existem dois reinos que parecem separados por um abismo misterioso. De um lado, a classe P — problemas que nossos computadores resolvem com elegância e rapidez. Do outro, a classe NP — problemas que parecem exigir busca exaustiva, mas cujas soluções, uma vez encontradas, são facilmente verificáveis. Como dois continentes separados por um oceano inexplorado, P e NP definem a geografia fundamental da complexidade computacional. Neste capítulo, exploraremos estes dois mundos, suas características únicas e a ponte enigmática que pode ou não conectá-los.
A classe P (de Polynomial time) contém todos os problemas que podem ser resolvidos em tempo polinomial por uma máquina de Turing determinística. Em termos práticos, são problemas para os quais conhecemos algoritmos eficientes. Quando dizemos "eficiente", significa que o tempo cresce como nᵏ para alguma constante k, onde n é o tamanho da entrada. Mesmo n¹⁰⁰ é considerado polinomial, embora impraticável — a definição é matemática, não necessariamente prática.
Por que polinômios definem eficiência? Polinômios têm propriedades matemáticas elegantes: a soma e composição de polinômios ainda são polinômios. Isso significa que algoritmos polinomiais podem chamar outros algoritmos polinomiais e permanecer eficientes. Além disso, para entradas práticas, algoritmos polinomiais geralmente terminam em tempo razoável, enquanto exponenciais rapidamente se tornam impraticáveis.
NP (Nondeterministic Polynomial time) contém problemas cujas soluções podem ser verificadas em tempo polinomial. Alternativamente, são problemas que uma máquina de Turing não-determinística resolveria em tempo polinomial. Imagine ter um oráculo que adivinha a resposta correta — NP são os problemas onde você pode rapidamente confirmar que o oráculo acertou.
Um certificado é uma prova sucinta de que a resposta para um problema é "sim". Para o problema de coloração de grafos com 3 cores, o certificado seria a atribuição de cores. Para fatoração, seriam os fatores. O verificador é um algoritmo polinomial que confere se o certificado é válido. Esta estrutura certificado-verificador é a essência de NP.
Claramente P ⊆ NP: se podemos resolver um problema rapidamente, certamente podemos verificar soluções rapidamente (basta resolver e comparar). A questão é se NP ⊆ P, ou seja, se P = NP. Esta inclusão reversa significaria que procurar é tão fácil quanto verificar — uma afirmação que contradiz nossa intuição e experiência diária.
A classe co-NP contém problemas cujo complemento está em NP. Por exemplo, se "o grafo tem clique de tamanho k" está em NP, então "o grafo NÃO tem clique de tamanho k" está em co-NP. Verificar que algo não existe é fundamentalmente diferente de verificar que existe — você não pode simplesmente apresentar um certificado de não-existência.
Formalmente, P e NP contêm apenas problemas de decisão (resposta sim/não). Problemas de otimização ("qual o menor caminho?") são convertidos em decisão ("existe caminho de comprimento ≤ k?"). Esta conversão preserva a complexidade essencial: se podemos decidir eficientemente para todo k, podemos otimizar via busca binária.
Máquinas não-determinísticas são uma abstração poderosa. Em cada passo, podem "adivinhar" a escolha correta entre várias opções. Equivalentemente, exploram todas as possibilidades em paralelo. Este paralelismo massivo e irrestrito é o que dá a NP seu poder aparente sobre P. Mas será este poder real ou ilusório?
Entre P e NP existe BPP (Bounded-error Probabilistic Polynomial time) — problemas resolvíveis em tempo polinomial com aleatoriedade e pequena chance de erro. Muitos acreditam que P = BPP, significando que aleatoriedade não adiciona poder computacional fundamental. Derandomização é o processo de remover aleatoriedade de algoritmos, área ativa de pesquisa.
Décadas de pesquisa produziram evidências circunstanciais de que P ≠ NP. Milhares de problemas NP-completos resistem a algoritmos eficientes. Oráculos relativizados separam P e NP. Mas também existem surpresas: problemas considerados difíceis (primalidade, programação linear) mostraram-se em P. A questão permanece fascinantemente aberta.
Se P ≠ NP, Ladner provou que existem problemas em NP que não estão em P nem são NP-completos — a zona intermediária NPI (NP-Intermediate). Candidatos incluem fatoração de inteiros e isomorfismo de grafos. Estes problemas têm estrutura especial que os impede de serem NP-completos, mas ainda resistem a algoritmos polinomiais.
As classes P e NP formam o coração da teoria da complexidade computacional. P representa o alcançável, o eficiente, o prático. NP representa o verificável, o buscável, o potencial. Entre eles está o maior mistério não resolvido da ciência da computação, uma questão que toca os fundamentos do que significa resolver problemas. Com este entendimento das duas classes fundamentais, estamos prontos para explorar a ponte que conecta problemas em NP: a redução polinomial!
Imagine que você sabe fazer pizza perfeitamente, mas alguém pede um calzone. Em vez de aprender uma receita totalmente nova, você percebe que um calzone é essencialmente uma pizza dobrada. Você transforma o problema desconhecido em um que já domina. Esta é a essência da redução polinomial — a técnica mais poderosa para comparar a dificuldade de problemas computacionais. Como alquimistas modernos, transformamos um problema em outro, preservando sua essência enquanto mudamos sua forma. Neste capítulo, dominaremos esta arte fundamental que conecta todos os problemas NP-completos.
Uma redução do problema A para o problema B é uma forma de resolver A usando uma solução para B. Se conseguimos transformar eficientemente instâncias de A em instâncias de B, então B é pelo menos tão difícil quanto A. É como dizer: "se você sabe dirigir um caminhão, certamente sabe dirigir um carro". A redução inverte nossa intuição — usamos o problema desconhecido B para resolver o conhecido A.
A redução polinomial mais comum, introduzida por Richard Karp, transforma a entrada inteira em tempo polinomial. Formalmente, A ≤ₚ B (A reduz polinomialmente a B) se existe função f computável em tempo polinomial tal que x ∈ A se e somente se f(x) ∈ B. Esta redução preserva pertinência: instâncias positivas mapeiam para positivas, negativas para negativas.
Exigimos que a transformação seja polinomial para preservar tratabilidade. Se A ≤ₚ B e B tem algoritmo polinomial, então A também tem: primeiro transformamos em tempo polinomial, depois resolvemos em tempo polinomial. Como polinômio composto com polinômio ainda é polinômio, obtemos algoritmo polinomial para A. Esta propriedade transitiva é crucial para a teoria.
Vejamos uma redução elegante de 3-SAT para CLIQUE. Dada uma fórmula com m cláusulas, criamos um grafo com 3m vértices (um para cada literal em cada cláusula). Conectamos vértices se: (1) vêm de cláusulas diferentes e (2) não são literais contraditórios. A fórmula é satisfatível se e somente se o grafo tem clique de tamanho m — cada vértice no clique corresponde a um literal verdadeiro satisfazendo sua cláusula.
Gadgets são componentes padronizados usados em reduções. Como peças de LEGO, podem ser combinados para construir transformações complexas. Um gadget comum é o "seletor de variável" — estrutura que força escolha entre verdadeiro/falso. Outro é o "verificador de cláusula" — garante que pelo menos um literal é verdadeiro. Dominar gadgets acelera drasticamente o design de reduções.
Um problema B é NP-difícil se todo problema em NP reduz polinomialmente a B. É NP-completo se, além disso, B ∈ NP. Os problemas NP-completos são os "mais difíceis" de NP — resolver qualquer um eficientemente resolveria todos. São equivalentes sob redução polinomial, formando a elite da dificuldade computacional.
A redução de Cook (Turing) permite múltiplas chamadas ao oráculo para B, não apenas uma. É mais poderosa mas menos comum para NP-completude. Por exemplo, problema de otimização pode usar decisão via busca binária — redução de Cook natural. Para NP-completude, preferimos Karp por ser mais restritiva e criar estrutura mais forte.
Construir reduções corretas requer cuidado. Erros frequentes incluem: reduzir na direção errada (de B para A em vez de A para B), transformação exponencial disfarçada, casos especiais não cobertos, e falha em preservar equivalência. Cada redução deve ser verificada meticulosamente — um erro invalida toda a prova de NP-completude.
Para problemas de otimização, existe redução que preserva aproximação. Se A reduz a B preservando aproximação, então algoritmo aproximado para B fornece algoritmo aproximado para A. Estas reduções são mais delicadas — devem preservar não apenas solução ótima, mas qualidade de soluções aproximadas.
Reduções revelam conexões profundas entre problemas aparentemente distintos. Coloração de grafos relaciona-se com satisfatibilidade booleana. Empacotamento conecta-se com cobertura. Roteamento liga-se a programação. Esta teia de reduções mostra que problemas NP-completos são manifestações diferentes de uma dificuldade computacional fundamental.
A redução polinomial é a linguagem universal da complexidade computacional. Como um dicionário que traduz entre idiomas, ela permite comparar problemas de domínios completamente diferentes. Dominar reduções é essencial para navegar o território da NP-completude. Com esta ferramenta poderosa em mãos, estamos prontos para encontrar o resultado que iniciou toda a teoria: o revolucionário Teorema de Cook-Levin!
Em 1971, dois cientistas trabalhando independentemente em continentes diferentes fizeram uma descoberta que mudaria para sempre a ciência da computação. Stephen Cook no Canadá e Leonid Levin na União Soviética provaram que o problema de Satisfatibilidade Booleana (SAT) é NP-completo — o primeiro problema identificado com esta propriedade. Como a descoberta de um elemento primordial do qual todos os outros podem ser formados, o Teorema de Cook-Levin estabeleceu SAT como o problema ancestral da NP-completude. Neste capítulo, exploraremos esta demonstração magistral que lançou mil reduções.
SAT pergunta se uma fórmula booleana pode ser satisfeita — existe atribuição de verdadeiro/falso às variáveis que torna a fórmula verdadeira? Por exemplo, (x ∨ y) ∧ (¬x ∨ z) é satisfatível com x=falso, y=verdadeiro, z=verdadeiro. Apesar da aparente simplicidade, SAT captura a essência de busca combinatória: encontrar configuração que satisfaça múltiplas restrições simultaneamente.
Cook e Levin tiveram a mesma percepção brilhante: qualquer computação de uma máquina de Turing não-determinística pode ser codificada como fórmula booleana. A fórmula é satisfatível se e somente se a máquina aceita. Como todo problema em NP é decidido por alguma máquina não-determinística polinomial, todos reduzem a SAT. Esta universalidade faz de SAT o problema NP-completo primordial.
Para máquina M executando em tempo t(n) com espaço s(n), criamos variáveis Q[i,q] (máquina no estado q no tempo i), H[i,j] (cabeçote na posição j no tempo i), e T[i,j,σ] (célula j contém símbolo σ no tempo i). São O(t(n)·s(n)) variáveis — polinomial quando M é polinomial. Cláusulas garantem configuração única, transições válidas e aceitação final.
Para garantir configuração bem-definida, precisamos que em cada momento i: exatamente um estado está ativo, cabeçote está em exatamente uma posição, cada célula contém exatamente um símbolo. Isto requer cláusulas "pelo menos um" (disjunção) e "no máximo um" (pares negativos). Por exemplo, (Q[i,q₁] ∨ Q[i,q₂] ∨ ... ∨ Q[i,qₖ]) garante algum estado ativo.
O coração da redução são cláusulas que codificam a função de transição δ. Se no tempo i a máquina está no estado q lendo símbolo σ, então no tempo i+1 deve estar no estado q', ter escrito σ', e movido adequadamente. Cada transição possível gera implicações: (Q[i,q] ∧ H[i,j] ∧ T[i,j,σ]) → (Q[i+1,q'] ∧ T[i+1,j,σ'] ∧ H[i+1,j±1]).
Visualize a computação como tableau bidimensional: linhas representam tempo, colunas representam posições na fita. Cada célula contém símbolo da fita naquele tempo-posição. A computação válida corresponde a tableau onde mudanças locais seguem regras da máquina. SAT verifica se existe tableau válido levando à aceitação.
Para máquina executando em tempo t(n), a fórmula tem O(t(n)²) variáveis e O(t(n)³) cláusulas. Quando t(n) é polinomial, a fórmula tem tamanho polinomial. Esta é a mágica: transformamos computação potencialmente complexa em fórmula de tamanho manejável. A construção é uniforme — mesmo algoritmo funciona para qualquer máquina.
SAT geral permite cláusulas de qualquer tamanho. 3-SAT restringe a exatamente 3 literais por cláusula, simplificando muitas reduções. Cook mostrou que 3-SAT também é NP-completo: cláusulas grandes são quebradas introduzindo variáveis auxiliares. Por exemplo, (a ∨ b ∨ c ∨ d) vira (a ∨ b ∨ y) ∧ (¬y ∨ c ∨ d) com nova variável y.
O Teorema de Cook-Levin foi o "Big Bang" da teoria de NP-completude. Antes, tínhamos problemas difíceis isolados. Depois, uma teoria unificada conectando milhares de problemas. Karp rapidamente mostrou 21 problemas NP-completos (1972). Hoje conhecemos milhares. O teorema transformou nossa compreensão da computação e continua influenciando pesquisa em algoritmos, criptografia e IA.
O teorema inspirou muitas variações. 2-SAT está em P (surpreendentemente). Horn-SAT e XOR-SAT também em P. MAX-SAT (maximizar cláusulas satisfeitas) é problema de otimização relacionado. #SAT (contar soluções) é #P-completo. QBF (fórmulas quantificadas) é PSPACE-completo. Cada variação ilumina diferentes aspectos da complexidade.
O Teorema de Cook-Levin é a pedra fundamental da teoria de NP-completude. Ao mostrar que SAT captura toda a complexidade de NP, Cook e Levin nos deram a chave para entender a dificuldade computacional. Como físicos que descobriram as leis fundamentais da natureza, eles revelaram a lei fundamental da complexidade. Com SAT como nosso problema primordial estabelecido, podemos agora explorar o rico zoológico de problemas NP-completos que dele descendem!
Como constelações no céu noturno da computação, os problemas NP-completos clássicos guiam navegadores do mundo algorítmico. Cada um conta uma história diferente, vem de um domínio distinto, mas todos compartilham a mesma essência misteriosa de dificuldade computacional. Do colorido mundo dos grafos às abstratas fórmulas booleanas, dos práticos problemas de empacotamento aos elegantes desafios numéricos, estes problemas formam o panteão da complexidade. Neste capítulo, conheceremos os protagonistas desta narrativa épica, entendendo suas peculiaridades e descobrindo as conexões surpreendentes entre eles.
Talvez o mais famoso problema NP-completo, o Caixeiro-Viajante (TSP) pede o menor tour visitando todas as cidades exatamente uma vez. Simples de entender, diabólico de resolver. Com n cidades, existem (n-1)!/2 tours possíveis — número que explode rapidamente. TSP modela desde roteamento de entregas até fabricação de chips, tornando-se símbolo da otimização combinatória.
Quantas cores precisamos para colorir vértices de um grafo sem que vizinhos tenham a mesma cor? Este problema aparentemente lúdico tem aplicações sérias em alocação de frequências, registradores de compiladores e agendamento. O caso k=2 é fácil (verificar bipartição), mas k=3 já é NP-completo. O famoso Teorema das Quatro Cores garante que mapas planares precisam no máximo 4 cores.
Dado conjunto de itens com pesos e valores, e mochila com capacidade limitada, maximize o valor total sem exceder o peso. Apesar da aparente simplicidade, Mochila é NP-completo (versão decisão). Modela alocação de recursos, investimentos, e até criptografia. A programação dinâmica resolve em tempo pseudo-polinomial O(nW), mas W pode ser exponencial em bits de entrada.
CLIQUE busca o maior subgrafo completo — conjunto de vértices todos conectados entre si. CONJUNTO INDEPENDENTE busca o maior conjunto sem arestas internas. São problemas duais: clique em G é conjunto independente em G complementar. Ambos modelam formação de grupos coesos, detecção de comunidades, e análise de redes sociais.
Encontrar o menor conjunto de vértices que "cobre" todas as arestas — cada aresta tem pelo menos um extremo no conjunto. Fundamental em vigilância (câmeras em corredores), redes (servidores em conexões), e biologia (proteínas em interações). VERTEX COVER está entre os "mais fáceis" dos NP-completos, com algoritmo 2-aproximado simples.
PARTIÇÃO pergunta se podemos dividir números em dois grupos de soma igual. SUBSET SUM pergunta se existe subconjunto somando valor específico. Apesar da simplicidade, capturam essência de problemas de balanceamento e alocação. Fundamentais em justiça distributiva, processamento paralelo, e criptografia de chave pública.
Existe caminho visitando cada vértice exatamente uma vez? E ciclo? Estes problemas gêmeos parecem similares a caminho/ciclo Euleriano (que são em P!), mas são NP-completos. A diferença crucial: Euler visita arestas, Hamilton visita vértices. Aplicações incluem sequenciamento de DNA, roteamento de robôs, e design de circuitos.
SET COVER: cobrir universo com mínimo de subconjuntos. HITTING SET: selecionar mínimo de elementos que "acertam" todos conjuntos. São duais e aparecem em facility location (onde construir lojas), teste de software (casos cobrindo funcionalidades), e diagnóstico médico (sintomas explicando doenças).
Conectar conjunto de terminais com árvore de peso mínimo, podendo usar vértices extras (Steiner). Generaliza árvore geradora mínima (P) para subconjunto de vértices. Fundamental em design de redes, VLSI, e filogenia. Variações incluem Steiner forest (múltiplas componentes) e directed Steiner tree.
Estes problemas clássicos formam uma teia intrincada de reduções. SAT reduz a 3-SAT, que reduz a CLIQUE, que reduz a CONJUNTO INDEPENDENTE, que reduz a VERTEX COVER. PARTITION reduz a SUBSET SUM, que reduz a KNAPSACK. Cada redução revela estrutura compartilhada, sugerindo que todos manifestam a mesma dificuldade fundamental de formas diferentes.
Os problemas NP-completos clássicos são como diferentes faces do mesmo diamante multifacetado. Cada um revela aspecto único da complexidade computacional, mas todos refletem a mesma luz fundamental. De grafos coloridos a mochilas cheias, de caixeiros viajantes a árvores de Steiner, estes problemas definem os limites do computável eficientemente. Com este repertório clássico em mente, estamos prontos para aprender as técnicas sofisticadas de demonstração que estabelecem novos membros neste clube exclusivo!
Provar que um problema é NP-completo é como escalar uma montanha intelectual com duas faces. Primeiro, mostrar que está em NP — geralmente a parte mais fácil, encontrando um certificado verificável. Depois, a escalada técnica: reduzir um problema NP-completo conhecido ao novo problema, preservando estrutura e complexidade. Como artesãos desenvolvendo habilidades refinadas ao longo de gerações, os teóricos da computação criaram um arsenal de técnicas elegantes para estas demonstrações. Neste capítulo, dominaremos estas ferramentas essenciais que transformam intuições sobre dificuldade em provas rigorosas.
Toda demonstração de NP-completude segue roteiro similar. Primeiro, prove pertinência a NP exibindo certificado polinomial e verificador. Segundo, escolha problema fonte NP-completo adequado — aquele cuja estrutura se assemelha ao problema alvo. Terceiro, construa transformação polinomial que preserve sim/não. Quarto, prove correção nos dois sentidos. Quinto, verifique que a transformação é realmente polinomial.
A escolha do problema fonte pode facilitar ou complicar drasticamente a redução. SAT é versátil mas pode gerar construções complexas. 3-SAT oferece estrutura mais regular. Para problemas de grafos, CLIQUE ou VERTEX COVER são boas opções. Para problemas numéricos, PARTITION ou SUBSET SUM. A experiência ensina quais fontes funcionam melhor para cada tipo de alvo.
Muitos problemas naturais são casos especiais de problemas mais gerais. Para provar NP-completude, mostramos que mesmo o caso restrito é difícil. Por exemplo, 3-COLORAÇÃO é NP-completo mesmo para grafos planares de grau máximo 4. A técnica envolve modificar a redução padrão para garantir que instâncias geradas satisfaçam as restrições especiais.
Gadgets são componentes padronizados que realizam funções específicas em reduções. Um gadget variável força escolha binária, gadget cláusula verifica satisfação local, gadget consistência propaga escolhas. Como circuitos eletrônicos construídos de componentes básicos, reduções complexas emergem da composição inteligente de gadgets simples.
Muitas reduções funcionam por substituição local: cada parte do problema fonte é substituída por gadget correspondente. A beleza está na modularidade — correção global emerge de correções locais. Por exemplo, reduzir 3-SAT para 3-COLORAÇÃO substitui cada variável e cláusula por subgrafos específicos, conectados apropriadamente.
Para problemas numéricos, frequentemente codificamos estrutura combinatória em números. Por exemplo, reduzir 3-PARTITION para BIN PACKING codifica partições em tamanhos de bins. O truque é escolher base numérica que previne "interferência" entre componentes diferentes. Números grandes garantem que soluções só existem com estrutura pretendida.
Provas de correção frequentemente requerem análise cuidadosa de casos. Para direção "se": assuma solução para instância original e construa solução para instância transformada. Para direção "somente se": assuma solução transformada e extraia solução original. Cada caso deve ser tratado rigorosamente, sem deixar lacunas.
Às vezes é mais fácil reduzir através de problemas intermediários. A ≤ₚ B ≤ₚ C implica A ≤ₚ C por transitividade. Mas cuidado: cada redução adiciona complexidade polinomial. Cadeias longas podem esconder crescimento super-polinomial. Sempre verifique que composição permanece polinomial.
Reduções elegantes preservam estrutura natural entre problemas. Cliques correspondem a conjuntos independentes no complemento. Coberturas de vértices correspondem a conjuntos independentes maximais. Estas correspondências naturais produzem reduções simples e intuitivas, além de revelar conexões profundas entre problemas.
Um erro sutil mas fatal é criar redução que parece polinomial mas não é. Cuidado com: número codificado em binário (tamanho log n), construções que geram objetos exponenciais, loops aninhados demais. Sempre calcule explicitamente o tamanho da instância gerada e o tempo de construção em função do tamanho da entrada original.
As técnicas de demonstração de NP-completude são as ferramentas do ofício para teóricos da complexidade. Como um carpinteiro que conhece quando usar martelo, serra ou plaina, o praticante experiente sabe qual técnica aplicar para cada situação. Dominar estas técnicas permite não apenas provar resultados novos, mas também apreciar a elegância das demonstrações clássicas. Com este arsenal técnico completo, podemos agora explorar o que fazer quando encontramos um problema NP-completo na prática: aproximar!
Quando a vida nos entrega um problema NP-completo, não podemos simplesmente desistir e ir para casa. Empresas precisam roteirizar entregas, fábricas devem sequenciar produção, redes requerem otimização — todos envolvendo problemas NP-completos. A salvação vem de uma percepção pragmática: frequentemente, uma solução muito boa é suficiente. Como navegadores que usam estrelas quando GPS falha, desenvolvemos algoritmos de aproximação e heurísticas que encontram soluções úteis em tempo razoável. Neste capítulo, exploraremos este arsenal prático que torna problemas intratáveis manejáveis no mundo real.
Um algoritmo α-aproximado garante solução no máximo α vezes pior que o ótimo (para minimização) ou pelo menos 1/α do ótimo (maximização). Por exemplo, algoritmo 2-aproximado para VERTEX COVER encontra cobertura com no máximo o dobro do tamanho mínimo. A beleza está na garantia: mesmo no pior caso, sabemos quão longe estamos do ideal.
Algoritmos gulosos fazem escolhas localmente ótimas esperando alcançar ótimo global. Surpreendentemente eficazes para muitos problemas NP-completos. Para SET COVER, escolher repetidamente o conjunto cobrindo mais elementos descobertos dá aproximação O(log n). Simples de implementar, rápidos de executar, frequentemente práticos.
Muitos problemas NP-completos são naturalmente programas inteiros. Relaxando para programação linear (polinomial!), obtemos limitante inferior/superior. Arredondando solução fracionária inteligentemente, conseguimos solução inteira aproximada. Esta técnica poderosa produziu alguns dos melhores algoritmos de aproximação conhecidos.
Começando de solução inicial, busca local melhora iterativamente explorando vizinhança. Para TSP, 2-opt troca pares de arestas reduzindo comprimento. k-opt generaliza. Não há garantia global, mas funciona bem na prática. Hill climbing, simulated annealing, e tabu search são variações sofisticadas que escapam de mínimos locais.
Algoritmos genéticos evoluem população de soluções via seleção e recombinação. Ant colony optimization imita formigas deixando feromônios. Particle swarm simula bandos explorando espaço de busca. Sem garantias teóricas, mas resultados impressionantes em problemas grandes e complexos do mundo real.
Um PTAS (Polynomial-Time Approximation Scheme) alcança aproximação (1+ε) para qualquer ε > 0, com tempo polinomial em n (mas possivelmente exponencial em 1/ε). FPTAS é polinomial também em 1/ε — o santo graal da aproximação. KNAPSACK tem FPTAS via programação dinâmica. TSP Euclidiano tem PTAS via decomposição geométrica.
Assumindo P ≠ NP, alguns problemas não admitem boa aproximação. CLIQUE não tem aproximação n¹⁻ᵋ para nenhum ε > 0. CHROMATIC NUMBER é inaproximável dentro de n¹⁻ᵋ. Estes resultados profundos usam PCPs (Probabilistically Checkable Proofs) e são tão difíceis de provar quanto importantes.
Conhecimento do domínio permite heurísticas especializadas superiores. Para roteamento de veículos, considerar horários de pico. Para alocação de tarefas, histórico de desempenho. Estas heurísticas "inteligentes" superam algoritmos genéricos, mas requerem expertise e customização.
Quando um parâmetro k é pequeno, algoritmos FPT (Fixed-Parameter Tractable) executam em tempo f(k)·nᴼ⁽¹⁾ — polinomial em n para k fixo. VERTEX COVER tem algoritmo O(2ᵏ·n). Para k pequeno, muito prático. Teoria de parametrização oferece alternativa elegante à aproximação.
Redes neurais aprendem heurísticas de instâncias resolvidas. Reinforcement learning descobre estratégias de busca. Graph neural networks capturam estrutura de problemas combinatórios. Sem garantias teóricas, mas resultados promissores combinando força bruta computacional com aprendizado de padrões.
Aproximação e heurísticas transformam a maldição da NP-completude em desafio manejável. Como médicos que não podem curar mas podem tratar, não resolvemos perfeitamente mas encontramos soluções suficientemente boas. A arte está em escolher a técnica certa: garantias teóricas quando precisamos certeza, heurísticas rápidas quando tempo é crítico, metaheurísticas quando qualidade é paramount. Com este arsenal prático, estamos prontos para explorar o rico mundo dos problemas NP-completos em grafos!
Grafos são a linguagem universal da conexão — de redes sociais a circuitos elétricos, de mapas rodoviários a interações proteicas. Não surpreende que muitos dos problemas NP-completos mais importantes e elegantes vivam no mundo dos grafos. Como joias em uma coroa matemática, estes problemas brilham com beleza estrutural enquanto desafiam nossos melhores algoritmos. Neste capítulo, exploraremos o rico ecossistema de problemas NP-completos em grafos, descobrindo padrões, conexões e os casos especiais raros onde a complexidade se dissolve.
Grafos modelam qualquer sistema de objetos e relações. Vértices representam entidades, arestas representam conexões. Esta simplicidade conceitual esconde complexidade computacional profunda. Perguntas aparentemente inocentes — "Qual o menor conjunto dominante?" ou "O grafo é 3-colorível?" — são NP-completas, enquanto outras similares — "Qual a menor árvore geradora?" — são facilmente resolvíveis.
CLIQUE busca o maior conjunto de vértices todos conectados entre si — o grupo mais coeso possível. Fundamental em análise de redes sociais (encontrar comunidades), bioinformática (complexos proteicos), e telecomunicações (frequências compatíveis). A dificuldade vem da natureza global: adicionar um vértice ao clique requer verificar conexão com todos os outros.
INDEPENDENT SET procura o maior conjunto sem arestas internas — vértices mutuamente não-adjacentes. É o dual de CLIQUE: conjunto independente em G é clique em G complementar. Modela alocação de recursos não-conflitantes, seleção de tarefas paralelas, e posicionamento de antenas sem interferência.
VERTEX COVER encontra o menor conjunto de vértices que "vigia" todas as arestas. Cada aresta deve ter pelo menos um extremo no conjunto. Apesar de NP-completo, admite aproximação 2 simples: repetidamente escolher aresta e adicionar ambos extremos. Fundamental em vigilância, monitoramento de redes, e alocação de recursos.
GRAPH COLORING atribui cores a vértices sem que vizinhos compartilhem cor. O número cromático χ(G) é o mínimo de cores necessárias. 2-COLOR está em P (testar bipartição), mas 3-COLOR é NP-completo. Aplicações incluem alocação de registradores, frequências de rádio, e scheduling de exames.
HAMILTONIAN CYCLE procura ciclo visitando cada vértice exatamente uma vez. Diferente de ciclo Euleriano (fácil!), não há caracterização simples. Dirac e Ore deram condições suficientes baseadas em graus, mas problema geral é NP-completo. Base do problema do caixeiro-viajante e sequenciamento de DNA.
DOMINATING SET busca menor conjunto S onde todo vértice está em S ou é vizinho de S. Modela posicionamento de torres de celular, localização de facilities, e disseminação de influência. Ainda NP-completo em grafos planares, mas polinomial em árvores. Não admite aproximação constante assumindo P ≠ NP.
FEEDBACK VERTEX SET remove mínimo de vértices para tornar grafo acíclico. Crucial em deadlock resolution, análise de circuitos, e constraint satisfaction. NP-completo mesmo em grafos de grau máximo 3. Admite FPT e aproximação 2. Em torneios (grafos direcionados completos), surpreendentemente tratável!
Certos tipos de grafos admitem algoritmos eficientes para problemas geralmente NP-completos. Árvores, grafos de intervalo, grafos cordais, cografos — cada classe tem estrutura especial explorável. Reconhecer estas classes e suas propriedades é crucial para resolver instâncias práticas eficientemente.
Treewidth mede quão "próximo de árvore" um grafo é. Grafos com treewidth limitado admitem algoritmos eficientes para muitos problemas NP-completos via programação dinâmica. Árvores têm treewidth 1, séries-paralelas têm 2, grades k×k têm k. Muitos grafos práticos têm treewidth pequeno.
MAX CUT particiona vértices maximizando arestas entre partes — NP-completo mas com 0.878-aproximação via SDP. MIN CUT está em P via algoritmos de fluxo. Esta dicotomia ilustra como problemas similares podem ter complexidades drasticamente diferentes. MULTIWAY CUT (separar k terminais) é NP-completo para k ≥ 3.
O mundo dos grafos é um laboratório perfeito para estudar NP-completude. Problemas fundamentais como CLIQUE e COLORAÇÃO revelam a dificuldade inerente de questões estruturais. Ao mesmo tempo, classes especiais como árvores e grafos cordais mostram que estrutura adicional pode tornar o difícil fácil. Esta dança entre complexidade e tratabilidade, entre o geral e o especial, é a essência da teoria dos grafos computacional. Com esta compreensão profunda, avancemos para ver como estes problemas teóricos impactam aplicações práticas!
A teoria da NP-completude não vive apenas em torres de marfim acadêmicas — ela pulsa no coração de sistemas que usamos diariamente. Cada vez que um aplicativo planeja sua rota, uma empresa otimiza sua logística, ou um compilador aloca registradores, problemas NP-completos estão sendo enfrentados e (aproximadamente) resolvidos. Como engenheiros construindo pontes sobre abismos intransponíveis, profissionais desenvolveram estratégias engenhosas para lidar com a intratabilidade teórica. Neste capítulo, exploraremos como a NP-completude se manifesta no mundo real e as soluções criativas que tornam o impossível possível.
O setor de logística enfrenta NP-completude diariamente. Roteirização de veículos (VRP) generaliza TSP para frotas com capacidades. Empresas como Amazon e FedEx resolvem instâncias com milhares de entregas usando heurísticas sofisticadas, metaheurísticas e decomposição. Economias de bilhões dependem de aproximações boas o suficiente de problemas teoricamente intratáveis.
Compiladores modernos enfrentam múltiplos problemas NP-completos. Alocação de registradores é coloração de grafos. Instruction scheduling é problema de ordenação com dependências. Apesar disso, compiladores produzem código eficiente usando heurísticas ajustadas, casos especiais tratáveis (SSA form), e aproximações rápidas. GCC e LLVM são milagres de engenharia navegando complexidade teórica.
A biologia molecular é rica em problemas NP-completos. Alinhamento múltiplo de sequências, predição de estrutura proteica, reconstrução filogenética — todos fundamentalmente difíceis. Pesquisadores usam heurísticas especializadas, conhecimento biológico, e computação massivamente paralela. Descobertas médicas emergem de soluções aproximadas destes problemas complexos.
IA encontra NP-completude em múltiplas frentes. Treinamento ótimo de redes neurais é NP-completo. Inferência em redes bayesianas gerais é NP-difícil. Feature selection é subset selection. Apesar disso, deep learning revoluciona o mundo usando gradiente descendente (mínimos locais), regularização, e arquiteturas especiais que tornam otimização tratável na prática.
Redes de telecomunicações enfrentam problemas NP-completos em design e operação. Alocação de frequências é coloração de grafos. Design de topologia envolve Steiner trees. Roteamento com QoS é multicommodity flow (fracionário em P, integral NP-completo). Provedores usam aproximações, relaxações, e engenharia cuidadosa para entregar serviços confiáveis.
Paradoxalmente, a segurança digital depende da dificuldade de problemas computacionais. RSA baseia-se em fatoração (NP ∩ co-NP, não conhecido ser NP-completo). Lattice-based crypto usa problemas NP-difíceis. Bitcoin mining é essencialmente busca por solução de problema NP. A intratabilidade que frustra em otimização protege em criptografia.
Projetar chips modernos com bilhões de transistores envolve numerosos problemas NP-completos. Placement é quadratic assignment. Routing é Steiner tree em grades. Clock tree synthesis, power optimization, timing closure — todos fundamentalmente difíceis. EDA tools usam hierarquia, particionamento, e heurísticas sofisticadas para tornar design possível.
Videogames escondem problemas NP-completos atrás de gráficos impressionantes. Pathfinding com obstáculos dinâmicos, NPC scheduling, geração procedural de níveis — todos computacionalmente desafiadores. Games usam A*, aproximações, e pré-computação extensiva. Até Sudoku e Minesweeper são NP-completos! Diversão emerge de complexidade computacional.
Mercados financeiros são campos de batalha de otimização NP-completa. Portfolio optimization com constrains é quadratic programming (NP-difícil). Arbitragem em mercados complexos, risk management, derivative pricing — todos envolvem problemas intratáveis. Bancos empregam exércitos de quants usando aproximações, Monte Carlo, e heurísticas para navegar complexidade.
Fábricas modernas são sinfonias de otimização enfrentando NP-completude. Job shop scheduling, assembly line balancing, cutting stock — problemas clássicos da pesquisa operacional. Indústria 4.0 usa IoT, ML, e otimização em tempo real para aproximar soluções. Toyota, Boeing, Intel — gigantes industriais construídas sobre soluções aproximadas de problemas exatos intratáveis.
Praticantes desenvolveram arsenal de técnicas para lidar com NP-completude: decomposição hierárquica, relaxação e fixing, warm starts, paralelização massiva, aprendizado de heurísticas, e exploração de estrutura especial. O segredo não é resolver perfeitamente, mas resolver bem o suficiente, rápido o suficiente, para necessidades práticas.
A NP-completude permeia tecnologia moderna, desde chips microscópicos até redes globais. Longe de ser curiosidade teórica, é realidade diária para engenheiros, cientistas, e desenvolvedores. O sucesso não vem de resolver estes problemas perfeitamente — impossível em escala — mas de navegá-los inteligentemente. Como marinheiros que não podem controlar o vento mas ajustam as velas, profissionais transformam intratabilidade teórica em soluções práticas. Com esta perspectiva aplicada, exploremos agora as fronteiras onde nossa compreensão da complexidade encontra seus limites!
Nos limites do conhecimento computacional, onde certezas se dissolvem em conjecturas e possibilidades quânticas dançam com limites clássicos, encontramos as fronteiras mais emocionantes da teoria da complexidade. Aqui, questões fundamentais sobre a natureza da computação, informação e realidade se entrelaçam. Computadores quânticos prometem revolucionar nossa relação com NP-completude. Novas classes de complexidade revelam horizontes inexplorados. Neste capítulo final, viajaremos às fronteiras onde o futuro da computação está sendo forjado.
Computadores quânticos exploram superposição e emaranhamento para processar informação de formas impossíveis classicamente. A classe BQP (Bounded-error Quantum Polynomial time) contém problemas resolvíveis eficientemente por computadores quânticos. Surpreendentemente, não sabemos se NP ⊆ BQP — computação quântica pode não resolver NP-completos eficientemente! Mas para problemas específicos como fatoração (algoritmo de Shor), oferece aceleração exponencial.
Quanto trabalho é necessário para provar que uma fórmula é insatisfatível? Proof complexity estuda o tamanho mínimo de provas em sistemas formais. Lower bounds para comprimento de provas implicariam P ≠ NP. Sistemas como Resolution, Cutting Planes, e Polynomial Calculus têm limitações conhecidas, mas provar limites para sistemas mais fortes permanece em aberto.
Quanto bits precisam ser trocados para computar função distribuída? Complexidade de comunicação tem conexões profundas com circuit complexity e proof complexity. Lower bounds em comunicação implicam lower bounds em outros modelos. Técnicas como discrepancy e information complexity revelam limites fundamentais de computação distribuída.
Circuitos booleanos oferecem modelo não-uniforme de computação. Provar que NP requer circuitos super-polinomiais implicaria P ≠ NP. Apesar de décadas de esforço, melhores lower bounds são apenas lineares para funções explícitas. Natural proofs barrier sugere que técnicas tradicionais são insuficientes contra circuitos com pseudorandomness.
Geometric complexity theory (GCT) aborda P vs NP através de geometria algébrica e teoria de representações. VP vs VNP é análogo algébrico de P vs NP. Permanent vs determinant exemplifica a separação conjecturada. Esta abordagem promete contornar barriers conhecidos, mas requer matemática sofisticada ainda em desenvolvimento.
IP = PSPACE mostrou que interação adiciona poder computacional imenso. PCPs (Probabilistically Checkable Proofs) revolucionaram nossa compreensão de provas e aproximação. Teorema PCP: NP = PCP(log n, 1) — toda prova tem versão checkável lendo apenas constante número de bits! Fundamental para inaproximabilidade e criptografia moderna.
Além de FPT, hierarquia W examina graus de parametrização. W[1] contém CLIQUE parametrizado, W[2] contém DOMINATING SET. Kernelization estuda pré-processamento polinomial. ETH (Exponential Time Hypothesis) e SETH (Strong ETH) postulam limites precisos para SAT, implicando lower bounds condicionais para muitos problemas.
Aprendizado PAC de conceitos simples pode ser NP-difícil. Treinar redes neurais otimamente é NP-completo. Mas na prática, SGD encontra soluções úteis. Por quê? Teoria emergente sugere que paisagens de loss têm estrutura especial, overparametrização ajuda, e implicit regularization guia para boas soluções. Interseção de ML e complexidade é fronteira ativa.
Computadores quânticos quebrarão RSA e criptografia de curvas elípticas. Alternativas baseadas em lattices, códigos, isogenias, e hash são consideradas quantum-resistentes. Muitas baseiam segurança em problemas NP-difíceis (mas não NP-completos!). NIST está padronizando algoritmos pós-quânticos. Futuro da privacidade digital depende de complexidade computacional.
Existem barreiras matemáticas profundas para resolver P vs NP. Relativização, naturalização, e algebrização mostram que técnicas tradicionais falham. Precisamos de "non-naturalizing non-relativizing non-algebrizing" proofs — ninguém sabe como são. Talvez P vs NP seja independente de ZFC, como continuum hypothesis. Ou talvez breakthrough está próximo.
As fronteiras da computação expandem em múltiplas direções. Computação quântica, biológica, e neuromórfica oferecem novos paradigmas. Complexidade de dados, streaming, e distribuída respondem a big data. Fine-grained complexity examina constantes. Complexity theory meets physics em holografia e termodinâmica. O futuro promete descobertas que redefinirão nossa compreensão de computação.
Nas fronteiras da computação, enfrentamos questões que tocam a natureza da realidade, informação e conhecimento. A NP-completude, nascida de questões práticas sobre algoritmos, evoluiu para lens através da qual examinamos limites fundamentais do universo computacional. Como exploradores em território desconhecido, cada descoberta revela novos mistérios. P versus NP permanece o Everest não escalado, mas a jornada para compreendê-lo transformou ciência da computação, matemática, e nossa visão do que é possível calcular. O futuro promete revoluções que mal podemos imaginar!
Este volume sobre NP-Completude foi construído sobre décadas de pesquisa fundamental em teoria da complexidade computacional. As referências abrangem desde os trabalhos pioneiros de Cook e Levin até desenvolvimentos contemporâneos em computação quântica e complexidade parametrizada. Esta bibliografia oferece recursos para aprofundamento em cada aspecto da NP-completude, desde fundamentos teóricos até aplicações práticas em otimização e inteligência artificial.
ARORA, Sanjeev; BARAK, Boaz. Computational Complexity: A Modern Approach. Cambridge: Cambridge University Press, 2009.
AUSIELLO, Giorgio et al. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Berlin: Springer, 1999.
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. Algorithms. New York: McGraw-Hill, 2008.
DOWNEY, Rod G.; FELLOWS, Michael R. 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.
HOCHBAUM, Dorit S. (Ed.). Approximation Algorithms for NP-Hard Problems. Boston: PWS Publishing, 1997.
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.
JOHNSON, David S. The NP-Completeness Column: An Ongoing Guide. Journal of Algorithms, v. 1-26, 1981-2007.
KARP, Richard M. Reducibility Among Combinatorial Problems. In: Miller, R. E.; Thatcher, J. W. (Eds.). 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.
LOVÁSZ, László. Combinatorial Problems and Exercises. 2nd ed. Amsterdam: North-Holland, 1993.
MENEZES, Nilo Ney Coutinho. Introdução à Programação com Python. 3ª ed. São Paulo: Novatec, 2019.
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. Quantum Computation and Quantum Information. 10th ed. Cambridge: Cambridge University Press, 2010.
PAPADIMITRIOU, Christos H. Computational Complexity. Reading: Addison-Wesley, 1994.
PAPADIMITRIOU, Christos H.; STEIGLITZ, Kenneth. Combinatorial Optimization: Algorithms and Complexity. Mineola: Dover Publications, 1998.
ROSEN, Kenneth H. Matemática Discreta e Suas Aplicações. 6ª ed. São Paulo: McGraw-Hill, 2009.
ROUGHGARDEN, Tim. Twenty Lectures on Algorithmic Game Theory. Cambridge: Cambridge University Press, 2016.
RUSSELL, Stuart; NORVIG, Peter. Inteligência Artificial. 3ª ed. Rio de Janeiro: Elsevier, 2013.
SCHAEFER, Thomas J. The Complexity of Satisfiability Problems. Proceedings of the 10th Annual ACM Symposium on Theory of Computing, p. 216-226, 1978.
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.
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de Dados e Seus Algoritmos. 3ª ed. Rio de Janeiro: LTC, 2010.
TREVISAN, Luca. Lecture Notes on Computational Complexity. Berkeley: University of California, 2011.
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.
VAN LEEUWEN, Jan (Ed.). Handbook of Theoretical Computer Science. Amsterdam: Elsevier, 1990. 2 v.
VAZIRANI, Vijay V. Approximation Algorithms. Berlin: Springer, 2003.
WEGENER, Ingo. Complexity Theory: Exploring the Limits of Efficient Algorithms. Berlin: Springer, 2005.
WILLIAMSON, David P.; SHMOYS, David B. The Design of Approximation Algorithms. Cambridge: Cambridge University Press, 2011.
WOLSEY, Laurence A. Integer Programming. 2nd ed. Hoboken: Wiley, 2020.
WOOLDRIDGE, Michael. An Introduction to MultiAgent Systems. 2nd ed. Chichester: John Wiley & Sons, 2009.
ZIVIANI, Nivio. Projeto de Algoritmos com Implementações em Pascal e C. 3ª ed. São Paulo: Cengage Learning, 2011.