Complexidade

Por que “complexidade” importa em IA

Quando um sistema de IA falha ao “escalar”, o gargalo muitas vezes não é a qualidade do modelo, mas a complexidade computacional (computational complexity): como o custo de tempo, memória ou comunicação cresce com o tamanho da entrada. A teoria da complexidade fornece um vocabulário para responder perguntas como:

  • Por que um método funciona com 10 mil itens, mas não com 10 milhões?
  • Existe alguma melhoria algorítmica disponível, ou o problema é inerentemente difícil?
  • Devemos buscar aproximações, relaxamentos ou formulações diferentes do problema?

Este artigo foca em tratabilidade (tractability), intuição sobre P vs NP (P vs NP intuition) e por que alguns problemas resistem à escalabilidade, com exemplos extraídos de aprendizado de máquina, busca e otimização.

Medindo custo: tempo, espaço e tamanho de entrada

Big-O (e afins)

Na análise de algoritmos, normalmente expressamos o tempo de execução como uma função do tamanho de entrada (n):

  • (O(\cdot)): limite superior assintótico (“cresce no máximo tão rápido quanto”, até constantes)
  • (\Theta(\cdot)): limite justo (“cresce como”)
  • (\Omega(\cdot)): limite inferior (“cresce pelo menos tão rápido quanto”)

Exemplos:

  • Ordenar (n) números: (\Theta(n \log n)) comparações (modelo de comparações)
  • Percorrer um array: (\Theta(n))
  • Verificar todos os pares: (\Theta(n^2))
  • Enumerar todos os subconjuntos: (\Theta(2^n))

A principal lição é que a taxa de crescimento domina. Um fator constante de 100× pode importar na prática, mas raramente se compara à diferença entre (n^2) e (2^n).

Tamanho de entrada é sutil: “número de itens” vs “número de bits”

Complexidade é definida em termos do comprimento da entrada, tipicamente medido em bits. Isso importa quando números podem ser grandes.

  • Se um algoritmo roda em tempo polinomial no valor numérico de um inteiro (digamos (W)), isso ainda pode ser exponencial no número de bits (\log W).
  • Essa distinção leva a ideias como tempo pseudo-polinomial (pseudo-polynomial time) (discutido abaixo).

Em sistemas de AM, “tamanho de entrada” pode ser:

  • número de pontos de dados (N)
  • dimensionalidade (d)
  • comprimento de sequência (L)
  • número de parâmetros (P)
  • número de classes (C)
  • tamanho do grafo (nós/arestas), etc.

Exemplo: escalonamento quadrático vs linear na prática

Calcular todas as distâncias par-a-par entre (n) embeddings é (O(n^2 d)). Isso se torna proibitivo rapidamente:

  • (n = 100{,}000) → ~(10^{10}) pares (já enorme)
  • (n = 1{,}000{,}000) → ~(10^{12}) pares (tipicamente impossível)

Por isso, sistemas de recuperação dependem de indexação e métodos aproximados em vez de “comparar com tudo”.

Conceitos relacionados aparecem em Algoritmos e Estruturas de Dados, especialmente em torno de indexação e estruturas de busca.

Tratabilidade: o que “eficiente” significa?

Tempo polinomial como linha divisória prática

Um problema costuma ser chamado de tratável (tractable) se puder ser resolvido em tempo polinomial (polynomial time) (por exemplo, (O(n)), (O(n^2)), (O(n^5))). Um problema costuma ser chamado de intratável (intractable) se os melhores algoritmos conhecidos levam tempo superpolinomial (super-polynomial) (por exemplo, (2^n), (n!)).

Por que focar em tempo polinomial?

  • Polinômios compõem bem: executar repetidamente uma sub-rotina em tempo polinomial frequentemente continua sendo tempo polinomial.
  • Exponenciais explodem mesmo para (n) modesto.
  • Muitas técnicas algorítmicas centrais (programação dinâmica, algoritmos em grafos, programação linear) fornecem limites polinomiais.

Mas tempo polinomial não garante usabilidade:

  • (O(n^6)) pode ser inútil em escalas realistas.
  • Fatores constantes e padrões de acesso à memória importam.
  • Paralelismo e hardware podem deslocar fronteiras.

Assim, em trabalho de sistemas, “tratável” frequentemente significa “cabe em orçamentos de latência/vazão/memória”, não apenas “está em P”.

Tempo pseudo-polinomial (importante em otimização)

Alguns algoritmos são polinomiais em valores numéricos (como capacidades ou custos), mas não no comprimento em bits da entrada.

Exemplo clássico: mochila (knapsack) pode ser resolvido por programação dinâmica em (O(nW)), onde (W) é a capacidade. Isso é eficiente quando (W) é pequeno, mas se (W) é enorme (e codificado em (\log W) bits), então (O(nW)) pode ser exponencial no verdadeiro tamanho de entrada.

Isso importa em IA quando você discretiza quantidades contínuas ou usa formulações de programação inteira.

Problemas de decisão e reduções: a linguagem da dificuldade

A teoria da complexidade frequentemente estuda problemas de decisão (decision problems) (perguntas de sim/não), porque são mais fáceis de classificar formalmente.

Exemplos:

  • “Existe uma rota mais curta que 10.000 km que visite todas as cidades?” (versão de decisão do TSP)
  • “Existe uma atribuição que satisfaça esta fórmula booleana?” (SAT)
  • “Existe um subconjunto de itens com peso total ≤ W e valor total ≥ V?” (decisão da mochila)

Reduções: mostrando que um problema é pelo menos tão difícil quanto outro

Uma redução em tempo polinomial (polynomial-time reduction) do problema A para o problema B significa:

Se conseguimos resolver B eficientemente, então conseguimos resolver A eficientemente (transformando A em B).

Então, se A é conhecido por ser difícil, e A reduz a B, então B também é difícil.

Reduções são a base de NP-completude (NP-completeness) e de muitos argumentos do tipo “isso não vai escalar”: você não precisa provar que B é difícil do zero — basta conectá-lo a um problema difícil conhecido.

Intuição sobre P vs NP (sem se perder na formalidade)

As classes P e NP

  • P: problemas de decisão solucionáveis em tempo polinomial.
  • NP: problemas de decisão em que uma solução proposta (“certificado”) pode ser verificada em tempo polinomial.

A famosa questão em aberto:

P vs NP: todo problema cuja solução pode ser verificada rapidamente também pode ser resolvido rapidamente?

A maioria dos cientistas da computação acredita que P ≠ NP, mas isso permanece não provado.

“Fácil de checar, difícil de encontrar”

A intuição central para NP é:

  • Se alguém lhe entrega uma solução candidata, você consegue checá-la rapidamente.
  • Mas encontrar essa solução pode exigir buscar em um espaço combinatório.

Exemplo: SAT

  • Dada uma atribuição de variáveis booleanas, verificar se ela satisfaz uma fórmula é rápido.
  • Mas encontrar uma atribuição satisfatória pode exigir explorar um número exponencial de possibilidades no pior caso.

NP-completo e NP-difícil

  • NP-completo (NP-complete): problemas que estão em NP e são tão difíceis quanto qualquer problema em NP (via reduções em tempo polinomial). Se algum problema NP-completo estiver em P, então P = NP.
  • NP-difícil (NP-hard): pelo menos tão difícil quanto problemas NP-completos, mas não necessariamente em NP (podem ser problemas de otimização ou até variantes indecidíveis).

Por que isso importa para escalar

Se sua tarefa é NP-difícil, você deve assumir que uma (ou mais) das seguintes coisas será necessária:

  • restringir o problema (casos especiais)
  • aceitar soluções aproximadas
  • usar heurísticas
  • explorar estrutura em instâncias reais
  • aceitar métodos probabilísticos/anytime
  • usar algoritmos exponenciais com poda e torcer para que instâncias típicas sejam pequenas/fáceis

Isso não é pessimismo — é realismo de engenharia informado por teoria.

NP-dificuldade aparece repetidamente em IA e AM

Muitas tarefas que parecem “aprendizado” ou “inferência” tornam-se NP-difíceis assim que você as enuncia como otimização combinatória exata.

Exemplo: agrupamento e problemas de atribuição discreta

  • k-means: o algoritmo padrão de Lloyd é rápido por iteração, mas a otimização subjacente (“encontrar o agrupamento k-means globalmente ótimo”) é NP-difícil em geral (mesmo em baixas dimensões para algumas variantes).
  • modelos de mistura (mixture models): atribuição exata ou ótimo global exato pode ser difícil; sistemas práticos dependem de heurísticas iterativas (EM, busca local).

Seleção de atributos e seleção de modelos esparsos

Selecionar o melhor subconjunto de atributos sob um orçamento é combinatório:

  • “Escolher os melhores (k) atributos” é, em geral, NP-difícil (relacionado à seleção de subconjuntos).
  • Alternativas práticas: regularização L1 (lasso), seleção gulosa progressiva, ou métodos embutidos.

Modelos gráficos: inferência exata e aprendizado de estrutura

Em modelos gráficos probabilísticos:

  • Inferência exata (por exemplo, computar probabilidades marginais) pode ser exponencial na estrutura do grafo (frequentemente ligada à largura de árvore (treewidth)).
  • Aprendizado de estrutura (encontrar o melhor grafo) é tipicamente NP-difícil.

Essa é uma das razões pelas quais métodos de inferência aproximada (inferência variacional, amostragem) são comuns.

Planejamento e busca

Muitos problemas de planejamento são NP-difíceis ou piores (PSPACE-completo é comum). Isso se conecta diretamente a Busca: quando você faz A* ou DFS com poda, frequentemente está gerenciando piores casos exponenciais com estrutura do problema e heurísticas.

Além de P vs NP: outros tipos de “difícil”

P vs NP não é a história toda. Em IA, você vai se deparar com:

  • PSPACE: problemas solucionáveis com memória polinomial (podem ainda exigir tempo exponencial). Muitos problemas de planejamento vivem aqui.
  • #P (sharp-P): contagem de soluções, frequentemente mais difícil do que decidir existência. Exemplo: contar atribuições satisfatórias (#SAT) é #P-completo.
  • Indecidibilidade (Undecidability): algumas perguntas sobre programas ou estruturas matemáticas gerais não podem ser resolvidas por algoritmo algum (menos comum em pipelines de AM mainstream, mas relevante em verificação).

Para muitos profissionais, a lição operacional é: mesmo que você consiga decidir viabilidade, contar ou obter probabilidades exatas pode ser muito mais difícil.

Complexidade em otimização contínua (onde o AM vive)

O treinamento em AM normalmente é formulado como otimização contínua, que tem seu próprio panorama de tratabilidade.

Convexo vs não convexo

  • Otimização convexa (convex optimization) tem garantias fortes; muitos problemas podem ser resolvidos eficientemente (tempo polinomial na teoria, bastante efetivo na prática).
  • Otimização não convexa (non-convex optimization) (comum em aprendizado profundo) não tem garantias de otimalidade global; existem resultados de dificuldade no pior caso para classes amplas de problemas.

Ainda assim, o aprendizado profundo funciona bem na prática porque:

  • o objetivo costuma ser boa generalização, não ótimos globais exatos
  • instâncias do problema têm estrutura
  • métodos estocásticos encontram soluções úteis

Ferramentas de otimização como Descida do Gradiente e questões numéricas cobertas em Computação Numérica importam aqui: um problema teoricamente “fácil” ainda pode falhar por condicionamento, precisão ou gradientes instáveis.

Verificação vs treinamento

Mesmo quando o treinamento funciona, verificar propriedades pode ser difícil:

  • verificar robustez de uma rede neural a perturbações adversariais é frequentemente NP-difícil para classes e normas comuns de redes (existem vários resultados formais).
  • ferramentas práticas usam relaxamentos (por exemplo, limites convexos) ou métodos incompletos.

Por que alguns problemas resistem à escalabilidade

Aqui estão barreiras comuns de escalabilidade, interpretadas pela lente da complexidade.

1) Explosão combinatória

Se o espaço de possibilidades cresce como (2^n), (n!) ou similar, adicionar mesmo uma pequena quantidade de entrada pode multiplicar o trabalho dramaticamente.

Exemplos:

  • seleção exata de subconjuntos sobre (n) atributos → (2^n) subconjuntos
  • rotas do caixeiro viajante sobre (n) cidades → (n!) rotas
  • busca exata em árvores de jogo pode explodir exponencialmente com a profundidade

Heurísticas podem ajudar, mas o crescimento no pior caso permanece.

2) Interações quadráticas (ou piores)

Alguns algoritmos são “apenas polinomiais”, mas ainda assim não escalam porque o expoente é grande demais.

Exemplos em IA:

  • autoatenção (self-attention) em Transformers vanilla é (O(L^2)) no comprimento de sequência (L), o que se torna um limite rígido para contextos longos. Isso motiva atenção esparsa, chunking, métodos com recuperação (retrieval-augmented) e outras mudanças arquiteturais (ver Arquitetura Transformer).
  • busca densa de similaridade entre todos os pares é (O(n^2)).

3) A maldição da dimensionalidade (complexidade efetiva)

Mesmo que um algoritmo seja polinomial em (d), a geometria de alta dimensão pode fazê-lo se comportar mal:

  • busca por vizinho mais próximo degrada em altas dimensões; indexação baseada em árvores se torna menos efetiva
  • amostragem e números de cobertura podem explodir com (d)

Isso é em parte complexidade e em parte geometria/estatística, mas frequentemente aparece como “não conseguimos escalar isso para espaços de atributos realistas”.

4) Memória e largura de banda, não apenas FLOPs

Às vezes o recurso limitante é:

  • memória (armazenar ativações, caches, índices)
  • E/S (carregamento de dados, checkpointing)
  • comunicação em rede (treinamento distribuído)

Esses também são problemas de “complexidade”: o custo pode escalar com parâmetros, tamanho de batch ou número de máquinas. Isso se conecta a Noções Básicas de Sistemas Distribuídos: escalar computação sem considerar comunicação pode falhar de forma inesperada.

5) Descompasso entre pior caso e caso típico

Um problema pode ser difícil no pior caso, mas frequentemente fácil em dados reais.

Solucionadores de SAT são um exemplo canônico:

  • SAT é NP-completo.
  • Ainda assim, solucionadores modernos de SAT lidam com muitas instâncias industriais com milhões de variáveis devido à estrutura, heurísticas e aprendizado de conflitos.

Por isso, a teoria da complexidade é um guia, não uma sentença de condenação: ela diz o que você não deveria esperar em geral, mas instâncias reais podem ter estrutura explorável.

O que fazer quando um problema é difícil: estratégias práticas

Quando teoria ou experiência sugerem que uma tarefa não vai escalar, respostas típicas incluem:

Use um algoritmo ou estrutura de dados melhor

Frequentemente os maiores ganhos vêm de trocar (O(n^2)) por (O(n \log n)) ou de computação densa para esparsa.

Exemplo: detecção de duplicatas por pares

  • ingênuo: comparar tudo com tudo ((O(n^2)))
  • prático: blocking, hashing, indexação, vizinhos mais próximos aproximados

Aqui Algoritmos e Estruturas de Dados é diretamente relevante.

Relaxe o problema (relaxamentos contínuos ou convexos)

Transforme uma otimização discreta em uma contínua, resolva eficientemente e faça o mapeamento de volta.

Exemplos:

  • relaxamentos de PL (LP) de programas inteiros
  • relaxamentos espectrais para agrupamento
  • perdas substitutas em classificação

Relaxamentos frequentemente trocam exatidão por escalabilidade e às vezes até melhoram a generalização ao evitar decisões discretas frágeis.

Aceite aproximação (com garantias quando possível)

Algoritmos de aproximação fornecem limites explícitos como:

  • “dentro de 1,5× do ótimo”
  • “dentro de ((1 - 1/e)) do ótimo”

Na prática de AM, você nem sempre terá razões formais de aproximação, mas a mentalidade é similar: pare de perseguir ótimos globais exatos quando o custo é exponencial.

Use heurísticas e algoritmos anytime

Heurísticas não garantem otimalidade, mas podem funcionar bem.

  • busca local, busca em feixe (beam search), recozimento simulado
  • métodos gulosos
  • branch-and-bound com poda
  • planejamento/busca guiados por heurísticas (ver Busca)

Algoritmos anytime são especialmente úteis: eles retornam uma solução válida rapidamente e a melhoram conforme recebem mais tempo.

Explore estrutura do problema ou parâmetros (complexidade parametrizada)

Às vezes um problema é difícil em geral, mas fácil quando certo parâmetro (k) é pequeno:

  • grafos com pequena largura de árvore
  • interações esparsas
  • número limitado de classes ou restrições

Um método pode ser tratável por parâmetro fixo (fixed-parameter tractable, FPT): exponencial em (k), mas polinomial em (n), por exemplo, (O(f(k),n^c)). Na prática, isso pode ser a diferença entre impossível e viável se (k) for naturalmente pequeno.

Mude a formulação: “Precisamos resolver *aquele* problema?”

Este é o movimento de engenharia mais importante. Muitos avanços de escalabilidade vêm de reenquadrar:

  • substituir vizinho mais próximo exato por recuperação aproximada
  • substituir otimização discreta global por substitutos diferenciáveis
  • substituir atenção densa por padrões esparsos ou aumento por recuperação
  • substituir inferência bayesiana exata por aproximações variacionais

A teoria da complexidade ajuda você a reconhecer quando reformular não é “trapaça”, mas o único caminho viável.

Um pequeno exemplo trabalhado: identificando uma armadilha \(O(n^2)\)

Uma armadilha comum é um loop aninhado aparentemente inocente:

def all_pairs_cosine_similarity(X):
    # X: n x d
    n, d = X.shape
    S = [[0.0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            S[i][j] = cosine(X[i], X[j])  # O(d)
    return S

Runtime: (O(n^2 d))
Memory: (O(n^2)) to store S

Isso “funciona” para (n=10{,}000) apenas se você tiver memória e tempo enormes; ele colapsa para (n=1{,}000{,}000).

Correções típicas:

  • computar apenas os top-k vizinhos (evitar saídas (n^2))
  • usar vizinhos mais próximos aproximados / indexação
  • fazer computações em batch e explorar GPUs (ajuda nas constantes, não na assíntota)
  • reduzir (n) via amostragem ou blocking

A lente da complexidade torna o problema central óbvio: você está tentando produzir uma saída de tamanho (n^2) — nenhuma micro-otimização vai salvá-lo.

Como pensar sobre complexidade em projetos de IA (um checklist)

Quando você encontrar problemas de escalabilidade, pergunte:

  1. Qual é o tamanho de entrada? (N, d, L, P), tamanho do grafo, etc.
  2. O que cresce mais rápido? Procure termos (N^2), (L^2) ou exponenciais.
  3. O gargalo é proporcional ao tamanho da saída? Se você precisa de saídas (O(n^2)), pode precisar de outro objetivo.
  4. Difícil no pior caso? Se a NP-dificuldade for provável, planeje heurísticas/aproximação.
  5. Dá para explorar estrutura? Esparsidade, baixo posto, largura de árvore limitada, faixas de parâmetros limitadas.
  6. Dá para relaxar ou reenquadrar? Substitutos diferenciáveis, inferência aproximada, recuperação em vez de varredura completa.
  7. Você está limitado por computação, memória ou comunicação? Escalar entre máquinas muda o formato do problema (ver Noções Básicas de Sistemas Distribuídos).

Resumo

Complexidade é o estudo de como o custo computacional cresce com o tamanho do problema. Em IA, ela explica por que algumas abordagens escalam suavemente enquanto outras batem em paredes rígidas:

  • Tempo polinomial é uma noção útil de tratabilidade, mas a praticidade no mundo real também depende de constantes, memória e hardware.
  • P vs NP captura uma lacuna fundamental entre “fácil de verificar” e “fácil de encontrar”, motivando por que muitas tarefas combinatórias exatas resistem à escalabilidade.
  • Muitas tarefas de IA (planejamento, inferência exata, seleção de subconjuntos, ótimos globais de agrupamento) se conectam a NP-dificuldade ou pior, empurrando profissionais para aproximações, heurísticas, relaxamentos e reformulações.
  • Falhas de escalabilidade frequentemente vêm de explosão combinatória, interações quadráticas, efeitos de alta dimensão ou limites de comunicação/memória — não apenas de computação insuficiente.

Quando bem usado, o pensamento em complexidade ajuda você a escolher algoritmos e desenhos de sistemas que permanecem viáveis conforme dados, modelos e exigências crescem.