A Arquitetura da Complexidade Computacional
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.
Nem todos os problemas matemáticos nascem iguais. Alguns se rendem facilmente aos nossos algoritmos, enquanto outros resistem teimosamente, exigindo recursos computacionais que crescem explosivamente com o tamanho da entrada. A teoria da complexidade computacional surgiu para mapear este vasto território de problemas, classificando-os em classes de acordo com os recursos necessários para resolvê-los. No coração desta classificação está a hierarquia polinomial, uma estrutura em camadas que organiza problemas de acordo com o número de alternações entre escolhas existenciais e universais necessárias para expressá-los. Esta torre majestosa de classes de complexidade não apenas organiza nosso conhecimento sobre problemas computacionais, mas também revela conexões profundas entre lógica, computação e os limites fundamentais do que podemos calcular eficientemente.
A complexidade computacional emergiu na década de 1960, quando pesquisadores perceberam que não bastava saber se um problema tinha solução — era crucial entender quão difícil era encontrá-la. Enquanto a computabilidade pergunta "o que pode ser calculado?", a complexidade questiona "o que pode ser calculado eficientemente?". Esta mudança de perspectiva transformou nossa compreensão da computação, revelando que muitos problemas importantes, embora teoricamente solúveis, exigem recursos proibitivos na prática.
Na teoria da complexidade, eficiência geralmente significa tempo polinomial — algoritmos cujo tempo de execução cresce como nᵏ para alguma constante k, onde n é o tamanho da entrada. Esta definição captura a intuição de que problemas tratáveis na prática devem ter algoritmos que escalam razoavelmente. Um algoritmo que leva n² passos pode ser viável para entradas grandes, mas um que requer 2ⁿ passos rapidamente se torna impraticável, mesmo para valores modestos de n.
A máquina de Turing, proposta por Alan Turing em 1936, fornece o modelo matemático preciso para definir complexidade. Uma máquina de Turing consiste em uma fita infinita dividida em células, uma cabeça de leitura/escrita, um conjunto finito de estados e regras de transição. Apesar de sua simplicidade, este modelo captura a essência da computação e permite definições rigorosas de tempo e espaço computacional.
Máquinas de Turing não-determinísticas possuem o poder mágico de fazer escolhas perfeitas — sempre adivinham corretamente o próximo passo que leva à solução, se ela existir. Embora não correspondam a computadores reais, o não-determinismo é uma ferramenta conceitual poderosa para classificar problemas. A diferença entre computação determinística e não-determinística está no cerne das questões mais profundas da complexidade.
Classes de complexidade agrupam problemas com características computacionais similares. A classe P contém problemas solúveis em tempo polinomial determinístico. NP abrange problemas verificáveis em tempo polinomial. PSPACE inclui problemas solúveis com espaço polinomial. Estas classes formam uma hierarquia, com inclusões conhecidas e separações conjecturadas que definem as fronteiras do nosso conhecimento.
Reduções são transformações que convertem instâncias de um problema em instâncias de outro, preservando a resposta. Se o problema A se reduz ao problema B, então B é pelo menos tão difícil quanto A. Reduções em tempo polinomial são especialmente importantes, pois preservam tratabilidade. Através de reduções, podemos identificar os problemas mais difíceis de cada classe — os problemas completos.
Um problema é completo para uma classe se pertence à classe e todo problema da classe se reduz a ele. Problemas completos capturam a essência computacional de suas classes. SAT (satisfatibilidade booleana) é NP-completo, representando a dificuldade máxima em NP. QBF (fórmulas booleanas quantificadas) é PSPACE-completo. Estes problemas servem como representantes canônicos de suas classes.
A hierarquia polinomial surgiu quando pesquisadores perceberam que nem todos os problemas em NP pareciam igualmente complexos. Alguns requerem apenas uma escolha não-determinística, outros parecem necessitar de alternações entre escolhas existenciais e universais. Esta observação levou à definição de níveis crescentes de complexidade, cada um capturando problemas com estrutura lógica mais intrincada.
A hierarquia polinomial tem conexões profundas com lógica matemática. Cada nível corresponde a fórmulas com um número específico de alternações de quantificadores. Esta correspondência revela que complexidade computacional e complexidade lógica estão intimamente relacionadas. Problemas mais altos na hierarquia requerem expressões lógicas mais sofisticadas para descrevê-los.
A hierarquia polinomial está repleta de questões em aberto. P = NP? A hierarquia colapsa em algum nível? Existem problemas em NP intermediários entre P e NP-completo? Estas perguntas não são meramente técnicas — suas respostas teriam implicações profundas para matemática, criptografia, inteligência artificial e nossa compreensão fundamental da natureza da computação.
Embora a hierarquia polinomial possa parecer abstrata, ela tem implicações práticas profundas. Problemas em diferentes níveis requerem abordagens algorítmicas distintas. Compreender onde um problema se situa na hierarquia guia o desenvolvimento de algoritmos, indica quando aproximações são necessárias e sugere que tipos de heurísticas podem funcionar.
A complexidade computacional transformou nossa compreensão dos limites da computação. A hierarquia polinomial, em particular, fornece uma lente através da qual podemos examinar a estrutura fina dos problemas computacionais. Como uma catedral gótica com suas torres e arcadas interconectadas, a hierarquia revela beleza na estrutura e profundidade nas conexões. Nos próximos capítulos, exploraremos cada andar desta magnífica construção intelectual, descobrindo os segredos que cada nível guarda e as pontes que os conectam!
No alicerce da hierarquia polinomial repousam duas classes fundamentais que moldaram décadas de pesquisa em ciência da computação: P e NP. Como os pilares gêmeos de um templo antigo, estas classes sustentam toda a estrutura da complexidade computacional moderna. P captura a noção intuitiva de problemas "fáceis" — aqueles que podemos resolver eficientemente. NP engloba problemas cujas soluções podemos verificar rapidamente, mesmo quando encontrá-las parece difícil. A relação entre estas duas classes constitui o enigma mais célebre da ciência da computação, uma questão cuja resposta vale um milhão de dólares e promete revolucionar nossa compreensão da computação.
P é a classe dos problemas de decisão solúveis por uma máquina de Turing determinística em tempo polinomial. Formalmente, um problema está em P se existe um algoritmo que, para entrada de tamanho n, produz a resposta correta em no máximo nᵏ passos para alguma constante k. Esta definição captura nossa intuição de tratabilidade — problemas em P têm soluções práticas que escalam razoavelmente com o tamanho da entrada.
Uma característica notável de P é sua robustez. A classe permanece inalterada sob variações razoáveis do modelo computacional. Máquinas de Turing com múltiplas fitas, máquinas de acesso aleatório, e até mesmo computadores quânticos para problemas de decisão clássicos — todos capturam essencialmente a mesma classe P. Esta invariância sugere que P captura algo fundamental sobre computação eficiente.
NP (Nondeterministic Polynomial time) contém problemas cujas soluções podem ser verificadas em tempo polinomial. Equivalentemente, são problemas solúveis por máquinas de Turing não-determinísticas em tempo polinomial. A beleza de NP está em sua caracterização dual: podemos pensar em termos de busca (encontrar solução) ou verificação (checar certificado).
NP abriga muitos problemas práticos importantes. SAT (satisfatibilidade booleana) pergunta se uma fórmula lógica tem atribuição verdadeira. O problema do caixeiro-viajante busca rotas eficientes. Coloração de grafos, clique máximo, mochila — todos residem em NP. Estes problemas surgem naturalmente em contextos práticos, tornando a compreensão de NP crucial para aplicações.
A noção de certificado é central para NP. Um certificado é uma prova sucinta de que a resposta é "sim". Para SAT, é uma atribuição satisfatória. Para Hamiltoniano, é o ciclo. O verificador é um algoritmo polinomial que checa o certificado. Esta estrutura — problema como busca, solução como certificado, verificação eficiente — permeia NP.
Stephen Cook e Leonid Levin independentemente descobriram que alguns problemas em NP são universais — todo problema em NP se reduz a eles. Estes problemas NP-completos representam o pináculo da dificuldade em NP. Se resolvermos qualquer um eficientemente, resolvemos todos. SAT foi o primeiro problema provado NP-completo, abrindo as comportas para milhares de outros.
P = NP? Esta pergunta aparentemente simples esconde profundidade oceânica. Se P = NP, encontrar soluções seria tão fácil quanto verificá-las. Provas matemáticas poderiam ser descobertas automaticamente. Criptografia moderna colapsaria. A maioria dos especialistas acredita que P ≠ NP, mas a prova permanece elusiva, resistindo aos melhores esforços de gerações de pesquisadores.
Décadas de pesquisa produziram evidências circunstanciais de que P ≠ NP. Milhares de problemas NP-completos resistem a algoritmos polinomiais. Resultados de complexidade de circuitos sugerem separação. Porém, barreiras técnicas — relativização, naturalização, algebrização — mostram que técnicas tradicionais são insuficientes. Novas ideias são necessárias.
co-NP consiste dos complementos de problemas em NP. Enquanto NP captura "existe solução?", co-NP pergunta "todas as tentativas falham?". UNSAT (insatisfatibilidade) e TAUTOLOGIA exemplificam co-NP. A relação entre NP e co-NP é sutil — se diferem, então P ≠ NP. Muitos acreditam que NP ≠ co-NP, mas provar isso é tão difícil quanto separar P de NP.
Assumindo P ≠ NP, o teorema de Ladner garante existência de problemas NP-intermediários — nem em P nem NP-completos. Estes problemas formam uma hierarquia infinita. Candidatos incluem fatoração, isomorfismo de grafos, e problemas de reticulados. A estrutura interna de NP é rica e complexa, muito além da dicotomia P/NP-completo.
Embora não conheçamos algoritmos polinomiais para problemas NP-completos, desenvolvemos arsenal sofisticado de técnicas. Algoritmos exponenciais melhorados, heurísticas, aproximações, casos especiais tratáveis — todos ajudam na prática. SAT-solvers modernos resolvem instâncias com milhões de variáveis, apesar da dureza teórica.
P e NP formam o coração pulsante da complexidade computacional. Como duas forças fundamentais da natureza computacional, elas definem os limites do que podemos calcular eficientemente e verificar rapidamente. A questão de sua equivalência transcende a matemática pura, tocando filosofia, prática computacional e os fundamentos do conhecimento. Compreender profundamente estas classes é essencial para apreciar a hierarquia polinomial que sobre elas se ergue, como veremos ao explorar os níveis superiores desta magnífica construção teórica!
Acima das fundações P e NP, ergue-se uma torre magnífica de classes de complexidade, cada andar capturando problemas com estrutura lógica progressivamente mais elaborada. A hierarquia polinomial organiza-se em níveis alternados Σₖᴾ e Πₖᴾ, onde k indica o número de alternações entre quantificadores existenciais e universais necessários para expressar o problema. Como uma escada em espiral ascendendo em direção ao infinito, cada nível revela novos panoramas de complexidade computacional, problemas que requerem raciocínio cada vez mais sofisticado para serem resolvidos ou mesmo compreendidos.
O nível k da hierarquia polinomial consiste de duas classes complementares: Σₖᴾ e Πₖᴾ. Formalmente, Σₖᴾ contém linguagens decididas por máquinas de Turing não-determinísticas de tempo polinomial com k-1 alternações, começando com estado existencial. Πₖᴾ é o complemento de Σₖᴾ. No primeiro nível, Σ₁ᴾ = NP e Π₁ᴾ = co-NP. Esta construção recursiva gera toda a hierarquia.
Uma das visões mais iluminadoras da hierarquia vem da lógica. Problemas em Σₖᴾ correspondem a propriedades expressáveis com k quantificadores alternados, começando com existencial. Por exemplo, Σ₂ᴾ captura problemas da forma "existe x tal que para todo y, R(x,y) vale", onde R é computável em tempo polinomial. Esta correspondência revela a natureza fundamentalmente lógica da complexidade computacional.
Σ₂ᴾ marca a primeira extensão genuína além de NP. Problemas aqui requerem poder computacional qualitativamente superior. Um exemplo clássico é determinar se uma fórmula booleana tem exatamente k atribuições satisfatórias — requer verificar existência e unicidade simultaneamente. Π₂ᴾ captura problemas duais, como verificar se toda extensão de uma atribuição parcial pode ser completada satisfatoriamente.
Cada nível da hierarquia possui seus problemas completos que caracterizam perfeitamente a complexidade daquele estrato. QBFₖ (fórmulas booleanas com k alternações de quantificadores) é Σₖᴾ-completo quando começa com ∃, e Πₖᴾ-completo quando começa com ∀. Estes problemas servem como pedras de toque para entender a dificuldade computacional em cada nível.
Entre os níveis principais residem classes intermediárias. Δₖᴾ = P^(Σₖ₋₁ᴾ) consiste de problemas solúveis deterministicamente com oráculo do nível anterior. Θₖᴾ permite consultas paralelas ao oráculo. Estas classes refinam nossa compreensão da hierarquia, revelando gradações sutis de complexidade entre os níveis principais.
Máquinas de Turing alternantes fornecem modelo computacional elegante para a hierarquia. Estados são existenciais ou universais. Computação forma árvore onde nós existenciais aceitam se algum filho aceita, universais se todos aceitam. Máquinas alternantes de tempo polinomial com k alternações capturam exatamente Σₖᴾ ou Πₖᴾ, unificando a visão computacional e lógica.
Um resultado fundamental estabelece que se a hierarquia polinomial é infinita, então cada nível é propriamente contido no próximo. Mais precisamente, se Σₖᴾ = Σₖ₊₁ᴾ para algum k, então PH = Σₖᴾ — a hierarquia colapsa no nível k. A maioria dos pesquisadores acredita que a hierarquia não colapsa, implicando infinitos níveis distintos de complexidade.
BPP (Bounded-error Probabilistic Polynomial time) contém problemas solúveis por algoritmos aleatorizados eficientes. Teorema de Sipser-Gács mostra BPP ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Muitos conjeturam BPP = P, o que colocaria aleatorização dentro do determinismo. A relação entre aleatorização e hierarquia polinomial permanece área ativa de pesquisa.
A hierarquia polinomial modela naturalmente jogos com número limitado de rodadas. Xadrez generalizado com k movimentos está no nível k. Problemas de planejamento com adversários, verificação de propriedades de sistemas, síntese de controladores — todos encontram expressão natural na hierarquia. A estrutura de alternação captura a essência de competição e cooperação.
A hierarquia polinomial está contida em PSPACE — problemas solúveis com memória polinomial. De fato, PH ⊆ PSPACE, e acredita-se que a contenção é própria. PSPACE captura QBF irrestrito (quantificadores ilimitados), enquanto cada nível de PH permite apenas número fixo de alternações. Esta diferença sugere separação, embora prová-la permaneça desafio monumental.
A hierarquia polinomial revela-se como uma estrutura de beleza matemática impressionante, onde lógica e computação entrelaçam-se em padrões cada vez mais complexos. Cada nível representa um salto qualitativo em poder expressivo, capturando problemas que requerem raciocínio genuinamente mais sofisticado. Como uma sinfonia onde cada movimento adiciona novas camadas de harmonia e complexidade, a hierarquia mostra como a alternação entre escolha e verificação cria um espectro rico de dificuldades computacionais. Compreender esta torre é essencial para apreciar os limites e possibilidades da computação eficiente!
Imagine ter acesso a uma caixa mágica que responde instantaneamente perguntas sobre um problema difícil. Este é o poder de um oráculo — uma abstração que permite explorar mundos computacionais hipotéticos onde certos problemas têm solução gratuita. O estudo de oráculos revolucionou nossa compreensão da hierarquia polinomial, revelando tanto sua robustez estrutural quanto as limitações fundamentais de certas técnicas de prova. Como telescópios apontados para universos paralelos, oráculos nos mostram que a verdade sobre P versus NP pode depender de métodos ainda não imaginados.
Um oráculo é um dispositivo hipotético que resolve um problema específico instantaneamente. Máquinas de Turing com oráculo podem consultar este dispositivo em um único passo computacional, independentemente da complexidade da pergunta. Notação Aᴮ representa a classe A com oráculo para B. Esta extensão permite explorar relações entre classes em mundos onde certos problemas são triviais.
A hierarquia polinomial pode ser definida elegantemente usando oráculos. Σₖ₊₁ᴾ = NPˢⁱᵍᵐᵃᵏᴾ — NP com oráculo para Σₖᴾ. Esta definição recursiva mostra como cada nível usa o poder do anterior como sub-rotina. A construção revela a natureza incremental da hierarquia: cada nível adiciona exatamente uma camada de não-determinismo sobre o anterior.
Uma propriedade relativiza se vale para todas as versões com oráculo das classes envolvidas. Surpreendentemente, muitas relações fundamentais relativizam, mas outras não. P ⊆ NP ⊆ PSPACE relativiza — vale para qualquer oráculo. Porém, existem oráculos A onde Pᴬ = NPᴬ e outros B onde Pᴮ ≠ NPᴮ. Esta descoberta abalou a comunidade, mostrando que certas técnicas jamais resolverão P versus NP.
Construir oráculos que separam classes requer engenhosidade. Para criar B onde Pᴮ ≠ NPᴮ, usa-se diagonalização. O oráculo é construído iterativamente, garantindo que alguma propriedade está em NPᴮ mas não em Pᴮ. A construção explora o poder do não-determinismo com o oráculo versus limitações do determinismo, mesmo com acesso ao mesmo oráculo.
Com probabilidade 1, um oráculo aleatório separa P de NP e mantém a hierarquia polinomial infinita. Este resultado profundo sugere que o mundo "típico" tem complexidade rica. Oráculos aleatórios fornecem intuição sobre o caso não-relativizado, embora não constituam prova. A técnica usa probabilidade para mostrar que separações são "genéricas".
Alguns oráculos causam colapsos dramáticos na hierarquia. Existe oráculo C onde PHᶜ colapsa para P^C. Outros oráculos fazem a hierarquia colapsar em níveis específicos. Estes resultados mostram que a estrutura da hierarquia não é absoluta, mas depende sutilmente do mundo computacional em que vivemos.
Refinamentos consideram número de consultas ao oráculo. P^(NP[k]) permite k consultas a NP. P^(NP[log n]) permite logaritmicamente muitas. Estas classes capturam trade-offs entre poder do oráculo e número de consultas. Hierarquias de consultas revelam estrutura fina entre classes principais, mostrando como informação limitada de problemas difíceis ainda ajuda.
Relativização estabelece barreiras fundamentais. Qualquer prova de P ≠ NP deve usar propriedades que não relativizam — deve explorar estrutura específica de computação sem oráculos. Isso elimina classes inteiras de abordagens. Diagonalização direta, argumentos de contagem simples, muitas técnicas combinatórias — todas relativizam e portanto são insuficientes.
BPP comporta-se peculiarmente com oráculos. Existe oráculo onde BPPᴬ não está contido em PHᴬ — aleatorização supera hierarquia inteira! Isso mostra que a relação entre aleatorização e não-determinismo é delicada e não-relativizante. Compreender BPP requer técnicas além de oráculos, explorando natureza específica de aleatorização.
Entre oráculos que colapsam e separam existem casos intermediários com comportamento sutil. Oráculos onde certas classes coincidem mas outras diferem. Oráculos que preservam algumas separações mas colapsam outras. Este zoológico de oráculos mostra a riqueza de mundos computacionais possíveis e a delicadeza das questões de complexidade.
Oráculos revelam simultaneamente o poder e os limites de nossa compreensão da hierarquia polinomial. Como sonhos lúcidos onde as leis da física podem mudar, mundos com oráculos mostram que muitas "verdades" sobre complexidade são contingentes, não necessárias. A barreira de relativização força-nos a buscar técnicas mais sofisticadas, que explorem a estrutura íntima dos problemas ao invés de propriedades genéricas. Esta busca por métodos não-relativizantes continua a impulsionar avanços na teoria da complexidade, prometendo que quando P versus NP for resolvido, a solução revelará insights profundos sobre a natureza da computação!
Em cada andar da hierarquia polinomial residem problemas que capturam perfeitamente a essência computacional daquele nível — os problemas completos. Como embaixadores de suas classes, estes problemas representam o máximo de dificuldade em seu estrato, servindo como pedras de toque para compreender a complexidade daquele nível. Resolver qualquer problema completo eficientemente resolveria todos os problemas do nível, fazendo deles os guardões dos segredos computacionais de suas classes. Neste capítulo, exploraremos estes problemas paradigmáticos, descobrindo como cada nível da hierarquia possui seus próprios desafios característicos.
As fórmulas booleanas quantificadas (QBF) formam a família mais natural de problemas completos para a hierarquia. QBFₖ, com k alternações de quantificadores, é completo para Σₖᴾ ou Πₖᴾ dependendo do quantificador inicial. Esta correspondência perfeita entre estrutura lógica e complexidade computacional não é coincidência — revela a natureza fundamentalmente lógica da hierarquia polinomial.
Circuitos booleanos fornecem rica fonte de problemas completos. Minimização de circuitos — existe circuito menor computando a mesma função? — é Σ₂ᴾ-completo. Equivalência de circuitos com tipos diferentes de portas gera problemas em vários níveis. A estrutura de circuitos, com sua hierarquia natural de complexidade, espelha belamente a hierarquia polinomial.
Jogos de soma zero com informação perfeita naturalmente habitam a hierarquia. Xadrez generalizado com k movimentos está no nível k. Determinar vencedor em jogos finitos alternados corresponde a resolver QBF com alternações correspondentes. Esta conexão torna a hierarquia relevante para IA de jogos e teoria dos jogos computacional.
Versões de otimização de problemas NP frequentemente sobem na hierarquia. Determinar o tamanho exato da maior clique é Δ₂ᴾ-completo. Verificar se uma solução é ótima pode ser Π₂ᴾ-completo. A transição de decisão para otimização frequentemente adiciona um nível de complexidade, ilustrando como encontrar o melhor é mais difícil que encontrar algo bom.
Comparar números de soluções gera problemas completos interessantes. Determinar se duas fórmulas têm o mesmo número de atribuições satisfatórias é C₂ᴾ-completo. Verificar se uma fórmula tem exatamente k soluções combina contagem com verificação, criando problemas Σ₂ᴾ-completos. A aritmética das soluções adiciona camadas de complexidade.
Planejamento com incerteza e adversários gera problemas em vários níveis. Existe plano que funciona independentemente das ações do ambiente? (Π₂ᴾ). Planejamento condicional com observações parciais sobe ainda mais na hierarquia. A presença de incerteza e escolhas adversárias naturalmente introduz alternações de quantificadores.
Raciocínio sobre conhecimento em sistemas multiagentes gera problemas completos interessantes. Determinar se um agente sabe que outro agente sabe algo introduz aninhamento que corresponde a níveis da hierarquia. Conhecimento comum e raciocínio epistêmico distribuído habitam níveis superiores, conectando lógica modal com complexidade computacional.
Consultas complexas em bases de dados frequentemente são completas para níveis da hierarquia. Consultas com negação estratificada, recursão limitada, ou agregação complexa mapeiam para diferentes níveis. Determinar se uma visão é atualizável, otimização de consultas, e problemas de integração de dados fornecem exemplos práticos de completude.
Verificação de propriedades de sistemas gera espectro de problemas completos. Verificar propriedades de segurança pode ser co-NP-completo, enquanto propriedades de vivacidade sobem na hierarquia. Model checking de lógicas temporais com alternação, síntese de sistemas reativos, e verificação de protocolos populam vários níveis.
Muitos problemas completos admitem caracterizações múltiplas que iluminam diferentes aspectos. SAT é NP-completo como busca, verificação, ou satisfatibilidade lógica. Estas perspectivas múltiplas enriquecem nossa compreensão e sugerem diferentes abordagens algorítmicas. Problemas completos servem como rosetas de pedra, traduzindo entre diferentes linguagens da complexidade.
Problemas completos são as estrelas-guia da hierarquia polinomial, marcando com precisão a dificuldade máxima de cada nível. Como obras-primas que definem movimentos artísticos, estes problemas caracterizam completamente suas classes, servindo tanto como exemplos paradigmáticos quanto como ferramentas para estabelecer completude de novos problemas. Compreender profundamente estes problemas é essencial para navegar a hierarquia e apreciar as sutilezas que distinguem cada nível. Eles nos lembram que a complexidade computacional não é abstração árida, mas teoria vibrante conectada a problemas práticos em jogos, otimização, verificação e raciocínio!
A hierarquia polinomial vive em delicado equilíbrio entre ordem e caos. Se certos eventos improváveis ocorressem — se P igualasse NP, se NP igualasse co-NP — toda a majestosa torre desmoronaria como um castelo de cartas, colapsando em estruturas mais simples. Por outro lado, provar que a hierarquia permanece infinita, com cada nível genuinamente mais complexo que o anterior, tem resistido a décadas de esforços. Este capítulo explora o fascinante mundo dos colapsos hipotéticos e separações conjecturadas, revelando como pequenas mudanças em nossas suposições podem ter consequências cataclísmicas para toda a estrutura.
Se Σₖᴾ = Πₖᴾ para algum k, então a hierarquia polinomial colapsa no nível k — PH = Σₖᴾ. Este resultado fundamental mostra a fragilidade da hierarquia: igualdade em qualquer nível propaga-se para cima, destruindo toda complexidade superior. A demonstração usa o fato de que Σₖ₊₁ᴾ = NPˢⁱᵍᵐᵃᵏᴾ, e se Σₖᴾ = Πₖᴾ, então podemos eliminar alternações superiores.
Se P = NP, a hierarquia inteira colapsa para P. Este seria o colapso mais dramático possível — toda a complexidade da hierarquia seria ilusória. Problemas considerados intratáveis teriam algoritmos eficientes. Criptografia moderna seria destruída. Matemática seria revolucionada com demonstrações automáticas. As implicações seriam tão profundas que a maioria acredita ser impossível.
Mesmo se NP = co-NP (mas P ≠ NP), a hierarquia colapsaria ao primeiro nível. Este cenário, embora menos dramático que P = NP, ainda seria surpreendente. Significaria que para todo problema em NP, tanto instâncias positivas quanto negativas teriam certificados curtos. Muitos problemas de otimização se tornariam mais tratáveis, pois verificar otimalidade seria tão fácil quanto verificar factibilidade.
A hierarquia pode colapsar parcialmente sem colapsar completamente. BPP = P colapsaria classes probabilísticas no determinismo sem afetar PH. AM = MA colapsaria ordem de interação em protocolos Arthur-Merlin. Estes colapsos parciais são considerados plausíveis e teriam implicações importantes mas não catastróficas.
Múltiplas linhas de evidência sugerem que a hierarquia não colapsa. Oráculos aleatórios mantêm PH infinita com probabilidade 1. Milhares de problemas naturais parecem genuinamente mais difíceis em níveis superiores. Conexões com outras áreas da matemática sugerem separações reais. Embora não conclusivas, estas evidências fortalecem a crença na infinitude da hierarquia.
Seinosuke Toda provou resultado surpreendente: PH ⊆ P#P. A hierarquia inteira está contida na classe de problemas solúveis com oráculo para contagem. Mais forte ainda: PH ⊆ P#P[1] — uma única consulta de contagem suficiente! Este teorema revela poder inesperado da contagem e sugere que #P captura algo fundamental sobre a hierarquia.
Se NP tem circuitos polinomiais (NP ⊆ P/poly), então PH colapsa para Σ₂ᴾ. Este teorema conecta uniformidade com não-uniformidade: se problemas NP têm circuitos pequenos (mesmo não-uniformes), a hierarquia colapsa dramaticamente. O resultado sugere que ou NP requer circuitos grandes, ou a hierarquia é finita — ambas conclusões significativas.
Várias hipóteses implicam que a hierarquia não colapsa. A hipótese do tempo exponencial (ETH) sugere que SAT requer tempo exponencial. A hipótese forte (SETH) refina isso. Hipóteses sobre geradores pseudo-aleatórios, lower bounds de circuitos, e dureza média — todas implicam ou sugerem que PH é infinita.
Sob várias hipóteses, podemos provar separações. Assumindo hipóteses de dureza, BPP = P. Assumindo hipóteses sobre geradores, certas classes probabilísticas colapsam. Estas separações condicionais fornecem roteiro: se provarmos as hipóteses, obteremos as separações. Isso foca esforços em problemas específicos e tratáveis.
Teoria dos modelos computacionais revela zoológico de mundos possíveis. Mundos onde P = NP mas NP ≠ co-NP. Mundos onde PH é infinita mas BPP = EXP. Mundos onde a hierarquia colapsa exatamente no nível 17. Estes mundos possíveis, embora improváveis, mostram a riqueza lógica da teoria e os limites do nosso conhecimento atual.
O estudo de colapsos e separações revela a hierarquia polinomial como estrutura simultaneamente robusta e frágil. Robusta porque resiste a décadas de ataques; frágil porque pequenas mudanças em fundamentos causariam colapsos dramáticos. Esta tensão entre estabilidade e precariedade torna a hierarquia fascinante. Como equilibrista em corda bamba, a hierarquia mantém seu equilíbrio delicado, desafiando-nos a entender se sua estrutura é necessária ou acidental. A busca por provas definitivas de separação ou colapso continua a impulsionar alguns dos desenvolvimentos mais profundos em ciência da computação teórica!
Quando a perfeição é inatingível, a aproximação torna-se arte. Diante de problemas NP-difíceis, frequentemente abandonamos a busca por soluções ótimas em favor de soluções aproximadas com garantias de qualidade. Surpreendentemente, a dificuldade de aproximação está intimamente ligada à estrutura da hierarquia polinomial. Alguns problemas admitem aproximações excelentes, outros resistem mesmo a aproximações grosseiras, e esta resistência frequentemente pode ser caracterizada em termos de níveis da hierarquia. Este capítulo explora a fascinante interação entre aproximação e complexidade estrutural.
Um algoritmo de aproximação produz soluções com garantia de qualidade em tempo polinomial. Para problema de minimização, algoritmo α-aproximado garante solução no máximo α vezes o ótimo. Para maximização, garante ao menos 1/α do ótimo. Esta relaxação da otimalidade frequentemente quebra barreiras de intratabilidade, permitindo soluções práticas para problemas difíceis.
Problemas NP-difíceis exibem espectro dramático de aproximabilidade. MAX-CUT admite 0.878-aproximação. Caixeiro-viajante métrico tem 1.5-aproximação. Clique máximo resiste a n^(1-ε)-aproximação para qualquer ε > 0, assumindo P ≠ NP. Esta variação sugere estrutura profunda diferenciando problemas aparentemente similares.
O Teorema PCP (Probabilistically Checkable Proofs) revolucionou nossa compreensão da aproximação. NP = PCP[O(log n), O(1)] — toda linguagem NP tem provas verificáveis lendo apenas posições constantes. Esta caracterização alternativa de NP imediatamente implica resultados de inaproximabilidade: muitos problemas não admitem aproximação melhor que certo limiar, assumindo P ≠ NP.
A Conjectura Unique Games postula dureza de problema específico de satisfação de restrições. Se verdadeira, implica resultados ótimos de inaproximabilidade para muitos problemas. MAX-CUT não admite aproximação melhor que 0.878. Vertex Cover não admite melhor que 2. A conjectura conecta aproximabilidade com estrutura da hierarquia de forma profunda.
Verificar qualidade de aproximação frequentemente está em Σ₂ᴾ. Determinar se existe solução 2-aproximada melhor que valor dado requer verificar que não existe solução muito melhor — quantificação alternada. Esta conexão mostra como aproximação naturalmente sobe na hierarquia, mesmo quando o problema original está em NP.
MAXSNP captura problemas de otimização expressáveis em fragmento específico de lógica. Todos admitem aproximação constante. MAX-3SAT, MAX-CUT, Vertex Cover pertencem a MAXSNP. Completude em MAXSNP sob L-reduções implica limiar de aproximação. Esta classe fornece teoria sistemática de aproximabilidade bounded.
Existe hierarquia de classes de aproximabilidade espelhando a hierarquia polinomial. Problemas com diferentes níveis de aproximabilidade correspondem a diferentes níveis de complexidade estrutural. Esta correspondência sugere que aproximabilidade e complexidade lógica estão fundamentalmente conectadas.
Técnicas modernas de aproximação exploram estrutura profunda. Programação semidefinida fornece relaxações poderosas. Rounding randomizado converte soluções fracionárias em inteiras. Primal-dual explora dualidade de LP. Métodos espectrais usam álgebra linear. Cada técnica tem conexões com níveis de complexidade.
Aproximação com informação limitada adiciona dimensão extra de complexidade. Algoritmos online devem decidir sem conhecer futuro. Algoritmos de streaming usam memória sublinhear. Estas restrições interagem com hierarquia de formas sutis, criando nova teoria de aproximação com recursos limitados.
Assumindo conjecturas da hierarquia polinomial, obtemos resultados fortes de inaproximabilidade. Se NP ⊈ DTIME(n^polylog(n)), certos problemas não admitem PTAS. Se a hierarquia não colapsa, outros problemas resistem a aproximações. Estas conexões mostram como estrutura global impacta aproximabilidade local.
Pesquisa atual explora fronteiras da aproximabilidade. Algoritmos quânticos para aproximação. Aproximação em modelos de computação não-convencionais. Conexões com machine learning e otimização contínua. Trade-offs entre qualidade e outros recursos. A teoria continua evoluindo rapidamente.
A teoria de aproximação revela dimensão fascinante da hierarquia polinomial. Quando abandonamos a perfeição, descobrimos novo espectro de complexidade, onde problemas superficialmente similares exibem comportamentos dramaticamente diferentes. A aproximabilidade não é acidente — está profundamente conectada com estrutura lógica e computacional. Como cartógrafos mapeando território parcialmente obscurecido, algoritmos de aproximação revelam contornos da paisagem computacional que permaneceriam invisíveis insistindo apenas em soluções exatas. Esta interação entre praticidade e teoria fundamental exemplifica a beleza da ciência da computação moderna!
Enquanto a hierarquia polinomial preocupa-se com existência — há uma solução? todas falham? — uma classe especial captura a complexidade de contar: #P. Quantas soluções existem? Quantos caminhos levam ao destino? Quantas colorações válidas? Estas questões de contagem revelam-se surpreendentemente poderosas, contendo em si toda a complexidade da hierarquia polinomial e além. Como um prisma que decompõe luz branca em espectro de cores, #P revela riqueza escondida em problemas aparentemente simples, mostrando que contar é fundamentalmente mais difícil que decidir.
A classe #P (pronunciada "sharp P") consiste das funções que contam soluções de problemas em NP. Formalmente, f está em #P se existe máquina de Turing não-determinística de tempo polinomial M tal que f(x) é o número de caminhos de aceitação de M em x. Diferentemente das classes de decisão da hierarquia, #P contém funções que retornam números naturais, não apenas sim/não.
#SAT conta atribuições satisfatórias de fórmulas booleanas. #HAM conta ciclos hamiltonianos em grafos. Permanent de matriz conta emparelhamentos perfeitos em grafos bipartidos. Cada problema NP tem versão #P natural — ao invés de perguntar "existe?", perguntamos "quantos?". Esta mudança aparentemente pequena frequentemente aumenta dramaticamente a dificuldade.
Um problema é #P-completo se está em #P e todo problema em #P reduz-se a ele. #SAT é #P-completo, servindo como problema universal de contagem. Surpreendentemente, alguns problemas com versão de decisão em P têm versão de contagem #P-completa. Permanent é #P-completo, embora decidir se permanent é não-zero esteja em P. Esta dicotomia revela que contar pode ser exponencialmente mais difícil que decidir.
O teorema de Toda estabelece que PH ⊆ P#P — a hierarquia polinomial inteira pode ser resolvida com oráculo para #P. Mais impressionante: uma única consulta suficiente! Isso mostra que contar é pelo menos tão poderoso quanto toda a hierarquia de alternações. A demonstração usa técnicas sofisticadas de amplificação e hashing.
O permanent de uma matriz soma produtos de todas as permutações, como o determinante mas sem sinais alternados. Enquanto determinante é computável em tempo polinomial, permanent é #P-completo. Esta diferença sutil — presença ou ausência de cancelamentos — separa tratabilidade de intratabilidade, ilustrando como pequenas mudanças algébricas têm enormes consequências computacionais.
Como contagem exata é frequentemente intratável, aproximação torna-se crucial. FPRAS (Fully Polynomial Randomized Approximation Scheme) fornece aproximação (1±ε) em tempo poly(n,1/ε) com alta probabilidade. Alguns problemas #P-completos admitem FPRAS (#DNF-SAT), outros parecem resistir (permanent de matrizes gerais). A aproximabilidade de problemas de contagem tem estrutura rica e misteriosa.
PP (Probabilistic Polynomial) decide se mais da metade dos caminhos aceitam — versão decisão de #P. ⊕P (Parity P) determina paridade do número de soluções. Ambas capturam aspectos diferentes de contagem. PP contém NP e co-NP, sendo extremamente poderosa. ⊕P tem comportamento peculiar, incomparável com muitas classes tradicionais.
Problemas de contagem conectam-se naturalmente com probabilidade. Contar configurações permite calcular probabilidades em espaços discretos. Inferência em redes bayesianas, volume de poliedros, probabilidade de confiabilidade — todos reduzem a contagem. Esta conexão torna #P central para IA probabilística e aprendizado de máquina.
Leslie Valiant introduziu algoritmos holográficos, técnica surpreendente para resolver casos especiais de problemas #P-completos em tempo polinomial. Usando transformações lineares e cancelamentos algébricos engenhosos, estes algoritmos resolvem problemas de contagem aparentemente intratáveis para grafos com estrutura específica. A técnica revela estrutura algébrica escondida em problemas combinatórios.
Complexidade parameterizada oferece visão refinada de #P. #W[1] captura contagem parameterizada difícil. Contar k-cliques é #W[1]-completo — difícil mesmo para k fixo. Alguns problemas admitem algoritmos FPT para contagem, outros parecem inerentemente difíceis. Esta teoria fornece mapa detalhado da paisagem de contagem.
Computação quântica oferece novas perspectivas sobre contagem. Algoritmos quânticos podem aproximar alguns problemas #P melhor que clássicos conhecidos. Amplitude de estados quânticos relaciona-se com contagem de caminhos. BosonSampling sugere que certos problemas de contagem são difíceis mesmo para computadores quânticos, fornecendo evidência de supremacia quântica.
A classe #P revela dimensão fascinante além da hierarquia polinomial tradicional. Contar transcende decidir, capturando complexidade que escapa às alternações de quantificadores. Como descobrir que cada floco de neve é único ao invés de apenas saber que neva, contar revela riqueza estrutural invisível na mera existência. O teorema de Toda mostra que esta riqueza é fundamental — contagem contém toda a complexidade da hierarquia e mais. Compreender #P é essencial para apreciar os limites verdadeiros da computação eficiente e as sutilezas que separam o tratável do intratável!
Além da hierarquia polinomial, que classifica por estrutura lógica, existem hierarquias fundamentais baseadas em recursos brutos: tempo e espaço. Estas hierarquias, estabelecidas por teoremas de diagonalização, garantem que mais recursos computacionais sempre permitem resolver problemas genuinamente mais difíceis. Como leis da termodinâmica computacional, estes teoremas estabelecem limites fundamentais e trade-offs entre recursos. Neste capítulo, exploraremos como tempo e espaço criam suas próprias torres de complexidade, interagindo sutilmente com a hierarquia polinomial.
O teorema da hierarquia de tempo determinístico afirma: para funções tempo-construtíveis f e g com g(n)log g(n) = o(f(n)), DTIME(g(n)) ⊊ DTIME(f(n)). Em palavras simples: com significativamente mais tempo, podemos resolver problemas genuinamente mais difíceis. A demonstração usa diagonalização — construindo problema que simula e inverte máquinas com menos tempo.
Teorema análogo vale para espaço: SPACE(g(n)) ⊊ SPACE(f(n)) quando g(n) = o(f(n)) para funções espaço-construtíveis. Notavelmente, não precisamos do fator logarítmico! Espaço é recurso reutilizável, permitindo simulação mais eficiente. Isso estabelece hierarquia estrita: L ⊊ PSPACE ⊊ EXPSPACE.
Tempo e espaço interagem de formas complexas. SPACE(s(n)) ⊆ TIME(2^O(s(n))) — configurações limitadas por espaço. TIME(t(n)) ⊆ SPACE(t(n)) — cada passo usa no máximo uma célula. Mas existem trade-offs genuínos: alguns problemas admitem algoritmos rápidos com muito espaço ou lentos com pouco espaço, mas não ambos.
Máquinas alternantes com recursos limitados geram hierarquias refinadas. ATIME(t(n)) com k alternações define nível k da hierarquia de tempo alternante. ASPACE(s(n)) = TIME(2^O(s(n))) — resultado surpreendente mostrando poder do espaço com alternação. Estas hierarquias conectam recursos brutos com estrutura lógica.
Entre P e PSPACE residem classes fascinantes. NC captura paralelismo eficiente. SC e RL exploram espaço e aleatoriedade limitados. Estas classes refinam nossa compreensão, revelando estrutura rica entre marcos principais. Cada classe captura modelo computacional ou restrição de recursos natural.
Não-determinismo cria suas próprias hierarquias. NTIME hierarquia estabelecida por teorema similar mas mais fraco — precisa fator n adicional. NP ⊊ NEXP provado, mas técnica não separa P de NP. Gap entre determinístico e não-determinístico permanece misterioso em cada nível.
Padding conecta problemas em diferentes níveis de recursos. Se P = NP, então EXP = NEXP — colapso propaga para cima. Técnica adiciona padding (preenchimento) transformando instância de tamanho n em tamanho 2ⁿ, movendo problema entre níveis. Padding mostra que separações em um nível implicam separações em outros.
Complexidade refinada estuda diferenças entre nᵏ para diferentes k. Conjecturas como SETH (SAT requer tempo 2ⁿ⁻ᵒ⁽¹⁾) implicam lower bounds precisos. Esta teoria revela estrutura dentro de P, distinguindo O(n²) de O(n²⁻ᵉ). Aplicações práticas abundam — algoritmos subquadráticos fazem diferença real.
Acima de EXP, torres de exponenciais continuam. 2-EXP, 3-EXP, ELEMENTARY (união de k-EXP). Cada nível tem problemas naturais — decidibilidade de lógicas, jogos complexos, verificação de sistemas. Mesmo problemas decidíveis podem requerer recursos astronômicos, tornando-os intratáveis na prática.
Hierarquias de recursos interagem sutilmente com hierarquia polinomial. PH ⊆ PSPACE, mas desconhecemos se PH = PSPACE. Se PH tem problemas completos sob reduções determinísticas, colapsa. Estas conexões mostram que estrutura lógica (PH) e recursos brutos (tempo/espaço) capturam aspectos complementares da complexidade.
As hierarquias de tempo e espaço fornecem espinha dorsal rígida para teoria da complexidade. Enquanto a hierarquia polinomial organiza por estrutura lógica, estas hierarquias garantem que mais recursos sempre permitem mais poder computacional. Como leis físicas do mundo computacional, estabelecem limites fundamentais e trade-offs inevitáveis. A interação entre diferentes tipos de hierarquias — lógicas, de recursos, probabilísticas — cria tapeçaria rica que é a moderna teoria da complexidade. Compreender estas múltiplas dimensões é essencial para apreciar verdadeiramente os limites da computação!
A hierarquia polinomial pode parecer construção teórica abstrata, mas suas ramificações permeiam tecnologia moderna, desde a segurança dos sistemas criptográficos até a eficiência de algoritmos de otimização industrial. Como a física quântica que, apesar de contra-intuitiva, fundamenta eletrônica moderna, a hierarquia polinomial fornece framework essencial para compreender e resolver problemas computacionais práticos. Neste capítulo final, exploraremos como estes conceitos aparentemente esotéricos impactam diretamente nossa vida digital, economia global e futuro tecnológico.
Segurança criptográfica moderna depende fundamentalmente da separação entre P e NP. RSA, Diffie-Hellman, criptografia de curvas elípticas — todos assumem que certos problemas são computacionalmente intratáveis. Se P = NP, estes sistemas colapsariam. Mas a hierarquia vai além: protocolos de conhecimento zero exploram a diferença entre NP e co-NP, assinaturas digitais dependem de problemas em níveis superiores.
Problemas de IA frequentemente habitam níveis superiores da hierarquia. Planejamento com incerteza é Σ₂ᴾ-completo. Inferência em redes bayesianas é #P-completo. Aprendizado PAC conecta-se com complexidade de circuitos. Compreender onde problemas de IA residem na hierarquia guia desenvolvimento de algoritmos, indica quando aproximações são necessárias, e sugere abordagens tratáveis.
Indústrias enfrentam diariamente problemas NP-difíceis. Roteamento de veículos, escalonamento de produção, alocação de recursos, design de redes — todos envolvem otimização complexa. Compreender estrutura destes problemas na hierarquia permite escolher abordagens apropriadas: quando usar programação linear, quando aplicar heurísticas, quando aceitar aproximações.
Análise de dados biológicos envolve problemas computacionalmente desafiadores. Alinhamento múltiplo de sequências, predição de estrutura de proteínas, reconstrução filogenética — muitos são NP-difíceis ou pior. Análise de redes metabólicas, design de drogas, medicina personalizada — todos requerem resolver problemas em vários níveis da hierarquia.
Sistemas críticos — aviônicos, médicos, financeiros — requerem verificação formal. Model checking, síntese de programas, verificação de protocolos envolvem problemas em vários níveis da hierarquia. Propriedades de segurança podem ser co-NP, vivacidade Σ₂ᴾ. Compreender complexidade guia escolha de técnicas: quando verificação completa é viável, quando testing suficiente.
Consultas complexas em bancos de dados massivos levantam questões de complexidade. Otimização de queries, view maintenance, integração de dados heterogêneos — problemas em diferentes níveis. Data mining, pattern discovery, privacidade diferencial adicionam camadas de complexidade. Compreender hierarquia permite projetar sistemas escaláveis.
Computadores quânticos prometem resolver alguns problemas mais rápido que clássicos. Mas onde BQP (problemas quânticos eficientes) se situa em relação à hierarquia? Acredita-se BQP ⊆ PP ⊆ P#P, sugerindo que quântico não resolve tudo em PH eficientemente. Compreender estas relações guia desenvolvimento de algoritmos quânticos e identificação de aplicações promissoras.
Teoria dos jogos algorítmica conecta economia com complexidade. Computar equilíbrios de Nash pode estar em níveis superiores da hierarquia. Leilões combinatórios, matching markets, mecanismos de votação — todos envolvem problemas computacionalmente desafiadores. Compreender complexidade informa design de mercados e instituições.
Internet enfrenta problemas de otimização constantemente. Roteamento, balanceamento de carga, alocação de bandwidth, segurança de rede — muitos são NP-difíceis. Content delivery, cloud computing, edge computing adicionam camadas de complexidade. Algoritmos aproximados e heurísticas, informados pela teoria, mantêm a internet funcionando.
Problemas de sustentabilidade frequentemente envolvem otimização complexa. Smart grids, energia renovável, redução de emissões — todos requerem resolver problemas difíceis. Planejamento urbano, transporte eficiente, economia circular envolvem trade-offs modelados por problemas em vários níveis da hierarquia.
Novas aplicações emergem constantemente. Blockchain e contratos inteligentes levantam questões de verificação. Realidade virtual/aumentada requer otimização em tempo real. Biologia sintética, nanotecnologia, exploração espacial — todos trarão novos desafios computacionais. A hierarquia polinomial continuará fornecendo framework para compreender e atacar estes problemas.
A hierarquia polinomial, longe de ser abstração acadêmica, é mapa essencial para navegar o mundo computacional moderno. Como cartografia que permite navegação, a hierarquia nos mostra onde problemas residem, que abordagens são promissoras, quando devemos aceitar aproximações. Cada aplicação tecnológica, cada avanço em IA, cada sistema seguro depende implicitamente desta compreensão. À medida que enfrentamos desafios cada vez mais complexos — mudança climática, medicina personalizada, inteligência artificial geral — a hierarquia polinomial continuará iluminando o caminho, distinguindo o possível do impossível, o tratável do intratável. Dominar estes conceitos não é apenas exercício intelectual, mas preparação essencial para moldar o futuro tecnológico da humanidade!
Este volume sobre a Hierarquia Polinomial representa síntese de décadas de pesquisa em complexidade computacional, desde os trabalhos pioneiros de Cook, Karp e Levin até desenvolvimentos contemporâneos em complexidade refinada e computação quântica. As referências abaixo oferecem recursos para aprofundamento em cada aspecto da hierarquia, desde fundamentos teóricos até aplicações práticas em inteligência artificial, criptografia e otimização.
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.
BAKER, Theodore; GILL, John; SOLOVAY, Robert. Relativizations of the P =? NP Question. SIAM Journal on Computing, v. 4, n. 4, p. 431-442, 1975.
BALCÁZAR, José Luis; DÍAZ, Josep; GABARRÓ, Joaquim. Structural Complexity I. 2nd ed. Berlin: Springer, 1995.
BEAME, Paul; PITASSI, Toniann. Propositional Proof Complexity: Past, Present and Future. Bulletin of the EATCS, v. 65, p. 66-89, 1998.
BÖRGER, Egon; GRÄDEL, Erich; GUREVICH, Yuri. The Classical Decision Problem. Berlin: Springer, 1997.
CAI, Jin-Yi; CHEN, Xi. Complexity Dichotomies for Counting Problems. Cambridge: Cambridge University Press, 2017.
CHANDRA, Ashok K.; KOZEN, Dexter C.; STOCKMEYER, Larry J. Alternation. Journal of the ACM, v. 28, n. 1, p. 114-133, 1981.
COOK, Stephen A. The Complexity of Theorem-Proving Procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, p. 151-158, 1971.
DOWNEY, Rod G.; FELLOWS, Michael R. Parameterized Complexity. New York: Springer, 1999.
DU, Ding-Zhu; KO, Ker-I. Theory of Computational Complexity. 2nd ed. Hoboken: Wiley, 2014.
EDMONDS, Jack. Paths, Trees, and Flowers. Canadian Journal of Mathematics, v. 17, p. 449-467, 1965.
FENNER, Stephen; FORTNOW, Lance; KURTZ, Stuart. Gap-Definable Counting Classes. Journal of Computer and System Sciences, v. 48, n. 1, p. 116-148, 1994.
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.
GREENLAW, Raymond; HOOVER, H. James; RUZZO, Walter L. Limits to Parallel Computation: P-Completeness Theory. Oxford: Oxford University Press, 1995.
HARTMANIS, Juris; STEARNS, Richard E. On the Computational Complexity of Algorithms. Transactions of the American Mathematical Society, v. 117, p. 285-306, 1965.
HÅSTAD, Johan. Some Optimal Inapproximability Results. Journal of the ACM, v. 48, n. 4, p. 798-859, 2001.
HEMASPAANDRA, Lane A.; OGIHARA, Mitsunori. The Complexity Theory Companion. Berlin: Springer, 2002.
IMMERMAN, Neil. Descriptive Complexity. New York: Springer, 1999.
IMPAGLIAZZO, Russell. A Personal View of Average-Case Complexity. In: 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.
KARP, Richard M.; LIPTON, Richard J. Turing Machines That Take Advice. L'Enseignement Mathématique, v. 28, p. 191-209, 1982.
KHOT, Subhash. On the Power of Unique 2-Prover 1-Round Games. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, p. 767-775, 2002.
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.
LUND, Carsten et al. Proof Verification and the Hardness of Approximation Problems. Journal of the ACM, v. 45, n. 3, p. 501-555, 1998.
MEYER, Albert R.; STOCKMEYER, Larry J. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. In: Proceedings of the 13th Annual Symposium on Switching and Automata Theory, p. 125-129, 1972.
MOTWANI, Rajeev; RAGHAVAN, Prabhakar. Randomized Algorithms. Cambridge: Cambridge University Press, 1995.
PAPADIMITRIOU, Christos H. Computational Complexity. Reading: Addison-Wesley, 1994.
PAPADIMITRIOU, Christos H.; YANNAKAKIS, Mihalis. Optimization, Approximation, and Complexity Classes. Journal of Computer and System Sciences, v. 43, n. 3, p. 425-440, 1991.
RAZBOROV, Alexander A.; RUDICH, Steven. Natural Proofs. Journal of Computer and System Sciences, v. 55, n. 1, p. 24-35, 1997.
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.
SIPSER, Michael. Introduction to the Theory of Computation. 3rd ed. Boston: Cengage Learning, 2013.
STOCKMEYER, Larry J. The Polynomial-Time Hierarchy. Theoretical Computer Science, v. 3, n. 1, p. 1-22, 1976.
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.
VALIANT, Leslie G. Holographic Algorithms. SIAM Journal on Computing, v. 37, n. 5, p. 1565-1594, 2008.
VAN MELKEBEEK, Dieter. Randomness and Completeness in Computational Complexity. Berlin: Springer, 2000.
VAZIRANI, Vijay V. Approximation Algorithms. Berlin: Springer, 2001.
WEGENER, Ingo. Complexity Theory: Exploring the Limits of Efficient Algorithms. Berlin: Springer, 2005.
WILLIAMS, Ryan. A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications. Theoretical Computer Science, v. 348, n. 2-3, p. 357-365, 2005.
WILLIAMSON, David P.; SHMOYS, David B. The Design of Approximation Algorithms. Cambridge: Cambridge University Press, 2011.
WRATHALL, Celia. Complete Sets and the Polynomial-Time Hierarchy. Theoretical Computer Science, v. 3, n. 1, p. 23-33, 1976.
YAO, Andrew Chi-Chih. Separating the Polynomial-Time Hierarchy by Oracles. In: Proceedings of the 26th Annual Symposium on Foundations of Computer Science, p. 1-10, 1985.