DEMONSTRAÇÕES TRANSPARENTES E A IMPOSSIBILIDADE DE APROXIMAÇÕES

Yoshiharu Kohayakawa

José Augusto R. Soares

Endereço dos autores:

Departamento de Ciência da Computação Instituto de Matemática e Estatística Universidade de São Paulo Rua do Matão 1010 Cidade Universitária 05508–900 São Paulo, SP

Endereços eletrônicos: <yoshi@ime.usp.br>, <jose@ime.usp.br>

PREFÁCIO

Uma linha de pesquisa em teoria da computação culminou recentemente com dois teoremas impressionantes. Informalmente falando, podemos enunciar estes resultados da seguinte maneira:

(i) Qualquer teorema dedutível em um sistema formal, como por exemplo a teoria dos conjuntos de Zermelo–Fraenkel ou a aritmética de Peano, admite uma demonstração em um novo sistema em que a sua correção pode ser verificada através do escrutínio de uma quantidade de caracteres não maior que uma constante universal.

(ii) A obtenção de uma solução aproximada para uma vasta gama de problemas de otimização combinatória é tão difícil quanto a obtenção de suas soluções exatas. De fato, estes problemas não admitem esquemas eficientes de resolução aproximada, a menos que P = NP.

O primeiro resultado acima é, sem dúvida, fascinante, e chega a parecer até um tanto paradoxal. Por outro lado, os leitores familiarizados com a teoria da complexidade computacional verão em (ii) um resultado comparável aos resultados clássicos de Cook, Levin, e Karp do começo da década de 70 em termos de impacto à teoria da computação: de fato, com este resultado a teoria P–NP é estendida ao âmbito muito mais genérico dos problemas de aproximação.

Surpreendentemente, os teoremas acima são intimamente ligados. Esta conexão inesperada entre (i) e (ii) e, mais geralmente, os avanços da teoria da complexidade computacional que levaram aos resultados acima são os nosso temas centrais.

Objetivamos com este pequeno texto dar uma introdução elementar aos assuntos aqui discutidos. Mantemos os pré-requisitos a um mínimo, e salientamos os aspectos menos técnicos desta área. Nem sempre discutimos em detalhe os resultados mais refinados, ou damos as demonstrações mais técnicas; entretanto, o conhecimento do material apresentado neste texto é, esperamos, mais que o suficiente para que os leitores interessados possam continuar seus estudos nesta linha de pesquisa. Aqueles que decidirem se aprofundar nesta área encontrarão aqui as referências mais importantes à literatura, que, aliás, cresce vigorosamente nesta direção. Cada capítulo termina com notas bibliográficas, onde fazemos uma breve discussão da literatura relevante.

Um tratado que desse uma visão global fiel de toda a área da teoria moderna da complexidade computacional seria bastante extenso—se o leitor puder usar estas notas como um ponto de partida, ou se pudermos com este texto interessar o leitor nesta área extremamente excitante de pesquisa, teremos atingido o nosso objetivo.

Agradecemos a participação entusiástica dos nossos colegas Paulo Feofiloff, Arnaldo Mandel e Claus Matsushigue numa série de seminários de estudo sobre o assunto abordado neste texto e à Coordenação do 20^{o} Colóquio Brasileiro de Matemática pela oportunidade de uma ampla divulgação.

Finalmente, é com prazer que agradecemos o apoio da FAPESP (Proc. 93/0603–1) e do CNPq (Projeto ProComb do ProTeM–CC, Fase II; Proc. 300334/93–1 e Proc. 300805/94–2).

Este texto foi preparado com AMS-L^{A}TEX, o sistema L^{A}TEX da American Mathematical Society, com o estilo amsbook.

Yoshiharu Kohayakawa José Augusto Soares

Abril de 1995

O segundo autor dedica este livro à Cássia.

CONTEÚDO

PREFÁCIO iii

Lista de Figuras ix

Capítulo I. INTRODUÇÃO 1

1. Discussão Inicial 2 1.1. Casando seus cavaleiros e donzelas 1.2. Os cavaleiros à mesa de jantar 1.3. Boas caracterizações 1.4. Efetividade e eficiência

2. Verificação Aleatória de Certificados 7 2.1. Provas interativas 2.2. Provas verificáveis probabilisticamente 2.3. Conseqüências para sistemas formais

3. Conseqüências para Problemas de Otimização 10 3.1. Problemas NP-difíceis 3.2. O problema do clique máximo

4. A Organização deste Texto 12

5. Notas Bibliográficas 13

vi CONTEÚDO

Capítulo II. PRELIMINARES 15 1. Modelos Computacionais 15

1.1. Tempo e espaço

1.2. Máquinas de Turing e RAM

2. As Classes P e NP 18 2.1. Sistemas de provas 2.2. A classe P 2.3. A classe NP 2.4. A classe PSPACE

3. Problemas de Enumeração e a Classe #P 23 4. Linguagens Recursivas 24

4.1. O problema da parada

5. Notas Bibliográficas 26 Capítulo III. PROVAS INTERATIVAS 27 1. Definições e Modelos 28

1.1. As classes IP e AM

1.2. Um exemplo de um sistema de prova interativo 1.3. Propriedades das classes IP e AM

2. coNP ⊂ IP 32 3. IP = PSPACE 37 4. Notas Bibliográficas 40 Capítulo IV. PROVAS VERIFICÁVEIS PROBABILIS-TICAMENTE 43 1. O Sistema de Provas PCP 43 2. A Estrutura da Demonstração 46 3. A Demonstração 48

3.1. Certificados transparentes I

3.2. Certificados transparentes II

3.3. Provas transparentes recursivas

4. Notas Bibliográficas 65

CONTEÚDO vii

Capítulo V. PROBLEMAS DE APROXIMAÇÃO 67 1. As Classes NPO, APX e EAP 68 2. Completude para Classes de Complexidade 70

2.1. Classe NP

2.2. Classes APX e EAP

3. Resultados de Inaproximabilidade 74 3.1. Resultados negativos para a classe APX 3.2. A impossibilidade de se aproximar o clique máximo 3.3. NP ⊆ PCP(log n, log n, n^{−ε})

4. Demonstrações dos Teoremas 44 e 45 84 5. Notas Bibliográficas 87 Apêndice A. LISTA DE PROBLEMAS 89 1. Problemas de Decisão 89 2. Problemas de Otimização 91 Apêndice B. DEFINIÇÕES 95 1. Notação Assintótica 95 2. Terminologia da Teoria dos Grafos 96 3. Terminologia da Lógica 97 REFERÊNCIAS 99 ÍNDICE REMISSIVO 104

viii CONTEÚDO

Lista de Figuras

II.1 Sistema de Provas 20

III.2 Sistema de Provas Interativo 29 III.3 Protocolo para Grafo Não-Isomorfismo 31 III.4 Protocolo lfkn 34 III.5 Protocolo para o Caso A 39 III.6 Protocolo para o Caso R 40 III.7 Operações sobre b 41

IV.8 O Teste de Linearidade 55 IV.9 As Funções Auto-Corretoras 57 IV.10 O Teste de Consistência 58 IV.11 O Teste de Satisfatibilidade 59

V.12 L-redução 73

x LISTA DE FIGURAS

CAPÍTULO I INTRODUÇÃO

O objetivo deste capítulo é o de fazer um apanhado geral dos tópicos de que trataremos neste texto. Seremos aqui informais, com o objetivo de tornar esta discussão inicial numa introdução descontraída aos temas centrais destas notas.

Dois são os temas principais que estudaremos neste texto. Estes temas podem ser classificados dentro de uma área fundamental da teoria da computação, a teoria da complexidade computacional. Brevemente falando, estamos nesta área interessados em estudar problemas computacionais do ponto de vista de seu custo de resolução. Resultados clássicos da lógica afirmam que certos problemas não podem ser resolvidos algoritmicamente. Temos em mente, por exemplo, o bem-conhecido ‘problema da parada’. O que nos interessa aqui são os problemas que podem ser resolvidos algoritmicamente, e a pergunta principal concerne à existência de algoritmos eficientes para resolvêlos.

Uma série de resultados impressionantes dentro da teoria de complexidade culminaram recentemente com uma nova caracterização de uma classe importante de problemas computacionais. Esta caracterização é o primeiro tema deste texto. O nosso segundo tema versa sobre o impacto surpreendente que este resultado tem sobre a solubilidade de uma vasta gama de problemas de otimização. Como uma conseqüência deste resultado, provou-se que muitos problemas clássicos de otimização combinatória não admitem resoluções algorítmicas eficientes, mesmo que aproximadas, a menos que a conjectura fundamental da teoria da computação conhecida como ‘P ≠ NP’ não seja correta. Em outras palavras, provou-se que, para muitos problemas de otimização combinatória, mesmo achar uma solução aproximada é tão difícil quanto achar uma solução exata.

1. Discussão Inicial

Seguindo a tradição nesta área, começamos a nossa discussão com uma fábula onde os personagens principais são o Rei Artur e Merlin.

1.1. Casando seus cavaleiros e donzelas. Um dia, o Rei Artur, em ótimo estado de espírito, tem a seguinte idéia. ‘Tenho na corte 150 cavaleiros e 150 donzelas. Por que não casá-los e ter então 150 casais?’ Sendo o Rei alguém de bom senso, ele pede que as donzelas elaborem, cada uma, uma lista de ‘parceiros aceitáveis’. O Rei compromete-se então a achar 150 casamentos que respeitem a preferência das donzelas. Nenhuma donzela terá como esposo um cavaleiro que não seja de seu agrado.

Vendo as 150 listas entregues a ele, o Rei Artur sente imediatamente uma dor de cabeça—o problema de achar os tais 150 casamentos parece muito complicado. Aqui entra na nossa estória o nosso segundo personagem. Merlin, o mago todo-poderoso, é chamado pelo Rei Artur para resolver este problema: nada é muito complicado para Merlin; ele pode, em um piscar de olhos, descobrir os tais 150 casamentos. Basta, pois, verificar se uma das 150! possibilidades serve.

Merlin pisca um olho, verifica que nenhuma das 150! bijeções serve, e assim informa ao Rei Artur. O Rei, tendo sempre um pouco de desconfiança de Merlin, diz: ‘Como? Impossível de se achar os meus 150 casamentos? Não pode ser; Merlin deve ter se esquecido de analisar alguma das possibilidades’. O Rei Artur é muito paciente, mas também muito ocupado. Ele não tem tempo de verificar todas as 150! = 5.7 …×10^{262} possibilidades ele mesmo.^{1} O que deve Merlin fazer para convencer o Rei Artur de que de fato nenhuma destas bijeções é uma solução ao problema? Merlin parece estar em apuros.

1Verificando uma bijeção por segundo, ele levaria 1.8 … × 10^{255} anos. A idade estimada do universo é da ordem de 10^{22} anos, e o número total de prótons no mundo conhecido é da ordem de 10^{79}.

Entretanto, lembrando-se repentinamente de suas aulas de teoria dos grafos da sua academia para magos, Merlin percebe o que fazer: basta usar o teorema de König! De fato, este teorema implica que tais 150 casamentos são possíveis se, e somente se, para qualquer subconjunto S de donzelas, o número de elementos na união das listas de parceiros aceitáveis das donzelas em S tem pelo menos |S| cavaleiros. Note que, de fato, se tal condição não for verificada, isto é, se houver um subconjunto de donzelas cuja união das listas correspondente tem menos que |S| elementos, então não podemos esperar casar todas estas donzelas respeitando as suas listas de preferência. Tal conjunto pode ser considerado como uma obstrução ao nosso objetivo.

A observação importante é que o teorema de König diz também que, por outro lado, se os 150 casamentos procurados não existem, então existe uma tal obstrução S. Como o Rei Artur pode facilmente julgar se um dado subconjunto S de donzelas é ou não uma obstrução, basta a Merlin fornecer ao Rei Artur uma tal obstrução S para ele convencer o nosso Rei de que, de fato, tais 150 casamentos não existem.

1.2. Os cavaleiros à mesa de jantar. O Rei Artur é forçado a se esquecer de sua ótima idéia de melhorar seu reino casando suas 150 donzelas com seus 150 cavaleiros. Entretanto, seu reino pode ser, percebe ele, melhorado de outro modo. Ao se sentarem à mesa para os seus importantes banquetes, os 150 cavaleiros comportam-se de forma menos que elegante quando a disposição dos lugares não é boa: dois cavaleiros que não se dão bem que por acaso fiquem em lugares adjacentes têm a forte tendência de acertarem suas diferenças antes do fim do jantar, de formas um tanto violentas (omitimos os detalhes). Como o único tipo de sangue que o nosso Rei gosta de ver nestes banquetes é aquele que vem com o seu bife mal passado, ele tem uma idéia. Por que não achar uma disposição de lugares para os seus 150 cavaleiros à mesa de forma que apenas cavaleiros amigos sentem-se um ao lado do outro?

Naturalmente, esta é uma nova tarefa para Merlin. O mago todopoderoso é chamado à presença do Rei Artur, e é-lhe dado a nova incumbência. Merlin pisca um olho, verifica as 150! possíveis disposições de lugares e descobre que, novamente, o Rei Artur deu-lhe uma tarefa impossível. Sabendo que o Rei não aceitará sua palavra apenas, ele pesquisa em suas notas de aula o que a teoria dos grafos tem a dizer sobre este problema. Merlin fica contente ao descobrir que este problema nada mais é que decidir se um certo grafo é hamiltoniano.

O grafo G em questão tem 150 vértices, um para cada cavaleiro, e ligamos dois deles com uma aresta se e só se os cavaleiros correspondentes aceitam-se mutuamente como vizinhos à mesa de jantar. A solução do problema é simplesmente um circuito hamiltoniano neste grafo, uma seqüência circular de vértices, contendo todos os 150 vértices de G, e tal que vértices adjacentes na seqüência são sempre adjacentes no nosso grafo.

Entretanto, Merlin fica surpreso ao saber que não se conhece uma boa caracterização de grafos hamiltonianos; nada como o resultado de König foi até hoje provado. Em outras palavras, não se conhece uma obstrução simples que necessariamente está presente em todo grafo que não contém um circuito hamiltoniano. Desta vez Merlin está realmente em apuros.

1.3. Boas caracterizações. Vimos na discussão acima que os dois problemas levantados pelo Rei Artur parecem ter, pelo menos dentro da teoria dos grafos, dois status diferentes. Na verdade, a teoria da complexidade computacional indica que estes dois problemas são intrinsecamente diferentes. Passemos a tratar os dois problemas do Rei Artur na linguagem da teoria dos grafos.

O primeiro problema corresponde a achar um emparelhamento perfeito em um certo grafo bipartido. De fato, consideremos B, um grafo bipartido com bipartição V (B) = X ∪ Y, onde X corresponde ao conjunto das 150 donzelas e Y ao dos 150 cavaleiros. A lista de possíveis parceiros de cada donzela corresponde no grafo B ao conjunto de vizinhos do vértice representando esta donzela. Achar os 150 casamentos do nosso Rei corresponde a achar um emparelhamento perfeito em B, i.e., um conjunto de arestas de B que incide sobre cada vértice exatamente uma vez. Por outro lado, como discutido acima, o segundo problema do Rei Artur corresponde a encontrar um circuito hamiltoniano em um certo grafo G. Consideremos por ora apenas os problemas de decidir se os objetos procurados, i.e., o emparelhamento perfeito e o circuito hamiltoniano, existem.^{2} Caso estes objetos existam, Merlin tem uma forma muito fácil de convencer o Rei deste fato. Basta exibir um tal objeto explicitamente, e o Rei simplesmente verificará se de fato o objeto apresentado é uma solução ao problema em questão. Em outras palavras, se a resposta ao problema de decisão for sim, há um certificado ‘simples’ para esta resposta, que pode ser verificado eficientemente.^{3}

2Tais problemas, cujas respostas são ou sim ou não, são conhecidos como ‘problemas de decisão’.

Caso um certo grafo bipartido B como acima não contenha um emparelhamento perfeito, Merlin pode exibir ao Rei Artur uma obstrução, cuja existência nos é garantida pelo teorema de König, e a inexistência da solução fica provada. Por outro lado, no caso do problema de decidir se um dado grafo G contém um circuito hamiltoniano, se a resposta for negativa, não se sabe como ‘provar’ este fato através de um ‘certificado’ eficientemente verificável. Em resumo, a resposta negativa ao primeiro problema pode ser certificada de forma simples, mas não se sabe, e suspeita-se que não seja possível, certificar a resposta negativa ao segundo problema.

Problemas de decisão que têm a característica de que a resposta sim pode ser eficientemente certificada são conhecidos como problemas da classe NP. Por outro lado, se a resposta a um problema for não e esta resposta puder ser certificada eficientemente, então dizemos que este problema pertence à classe coNP. Assim, o problema de decidir se um dado grafo bipartido contém um emparelhamento perfeito pertence tanto à classe NP como à classe coNP. O problema de decidir se um circuito hamiltoniano existe em um dado grafo pertence à classe NP, mas suspeita-se que ele não pertença à classe coNP.

Como tanto a existência como a inexistência de emparelhamentos perfeitos em grafos bipartidos admitem certificados eficientemente verificáveis, ou, na linguagem introduzida acima, o problema de decisão correspondente está tanto em NP como em coNP, dizemos que a existência destes objetos admite uma boa caracterização. Este conceito foi introduzido na década de 60, nos primórdios da otimização combinatória e da teoria de complexidade.

Um problema de aparência inocente, mas cuja solução teria conseqüências profundas em teoria da computação, é o de decidir se a existência de circuitos hamiltonianos admite uma boa caracterização.

3Em nossa fábula, o Rei Artur representa um ente que está disposto a executar procedimentos eficientes, enquanto que Merlin representa um ente capaz de executar qualquer procedimento computacional.

1.4. Efetividade e eficiência. Na discussão até o momento, temos usado o termo eficiente sem maiores discussões. Devemos neste ponto fazer alguns comentários a esse respeito. Na década de 30, a lógica estava descobrindo a existência de problemas que não podiam ser resolvidos ‘algoritmicamente’ ou ‘efetivamente’. O mais famoso deles é, talvez, o Entscheidungsproblem de Hilbert: dado um sistema formal e uma afirmativa dentro deste sistema, pode esta afirmativa ser provada dentro deste sistema?

Os problemas nos quais a teoria da computação tem interesse são essencialmente sempre efetivamente solúveis. Tipicamente, o conjunto das possíveis soluções para uma dada ‘instância’ do problema é finito e bem conhecido, e uma busca exaustiva neste espaço das possibilidades constitui um processo efetivo de se resolver o problema em questão com aquela particular entrada. Entretanto, o espaço das possibilidades quase sempre cresce de forma muito rápida com o ‘tamanho’ da instância a ser resolvida. Por exemplo, se o Rei Artur tivesse apenas 5 cavaleiros, o problema do ‘banquete pacífico’ poderia ser resolvido pelo próprio Rei com um pouco de paciência, mas, como vimos, com os seus 150 cavaleiros, uma tentativa ingênua de se achar um circuito hamiltoniano é fadada ao fracasso, dado o grande número de possibilidades a serem verificadas. Esta explosão do espaço das possibilidades é típico em problemas computacionais de interesse.

Em teoria da computação, a noção aceita de ‘eficiência’ é a seguinte: dizemos que um algoritmo que resolve um problema é eficiente se o tempo do qual este algoritmo precisa para resolver uma instância de ‘tamanho’ n é limitado por algum polinômio em n. Isto é, se existe alguma constante k tal que o tempo de computação para qualquer entrada de tamanho n é limitado por n^{k} para n suficientemente grandes. Aqui, o tamanho da instância é o número de bits que são necessários para se codificar a entrada em algum sistema ‘sensato’ de codificação, e medimos o tempo usado pelo algoritmo de alguma forma ‘sensata’.^{4} Esta noção de eficiência não deve ser interpretada como um critério prático; um algoritmo polinomial não é necessariamente utilizável em aplicações reais. Este critério tem sido, entretanto, muito frutífero do ponto vista teórico. A classe dos problemas para os quais existem algoritmos polinomiais é conhecida como a classe P.

4Definições precisas serão dadas no Capítulo II.

No que segue, usamos o termo ‘eficiente’ para significar ‘polinomial’. Em particular, na nossa fábula, admitimos que o Rei Artur é capaz de executar procedimentos polinomiais apenas, enquanto que Merlin é capaz de executar qualquer procedimento efetivo.

2. Verificação Aleatória de Certificados

2.1. Provas interativas. Nesta seção voltamos à nossa fábula. Temos agora Merlin tentanto descobrir como convencer o Rei Artur de que não existe uma disposição pacífica de seus 150 cavaleiros. Vimos na Seção 1.3 que não se sabe se a inexistência de circuitos hamiltonianos admite um certificado facilmente verificável, ou, em outros termos, não se sabe se há um meio de Merlin convencer o Rei Artur deste fato.

Uma descoberta recente de múltiplas conseqüências é que se o Rei Artur tiver acesso a um gerador de números aleatórios, e se ele estiver disposto a conversar (‘interagir’) com Merlin por algum tempo, então há uma forma de Merlin convencer o Rei Artur da inexistência de uma solução ao seu problema dos banquetes pacíficos.

Grosseiramente falando, existe um ‘jogo’ que o Rei Artur e Merlin podem jogar que resulta na vitória certa de Merlin se de fato não existe um circuito hamiltoniano no grafo em questão, como afirmado por ele, e que resulta em vitória quase certa do Rei Artur se Merlin está enganado. Esta segunda possibilidade é de natureza probabilística: uma afirmativa mais precisa é que se existe o circuito hamiltoniano em questão, então a probabilidade de o Rei Artur vencer é tão grande quanto se queira; digamos, ela é de pelo menos 99%, sendo o 1% restante devido ao eventual ‘azar’ do Rei Artur com o seu gerador de números aleatórios. Uma outra característica deste jogo é que ele é um procedimento eficiente: o Rei Artur e Merlin alternam os seus lances, o Rei Artur precisa apenas fazer computações de complexidade polinomial, e o número de lances total no jogo é também polinomial.

Um teorema geral é como segue. Suponha que temos um objeto cuja existência admite um certificado verificável eficientemente, i.e., o problema de decisão correspondente pertence a NP. Então a inexistência deste objeto admite uma prova interativa, ou seja, um jogo com as características acima.

Na verdade, descobriu-se que a classe de afirmativas que admitem provas interativas é extremamente grande. De fato, o resultado final nesta direção é que IP, a classe das afirmativas que admitem provas interativas, é idêntica à classe PSPACE, a classe das afirmativas cujas demonstrações podem ser encontradas por procedimentos que usam espaço apenas polinomial, sem restrição no tempo de computação. Acredita-se fortemente que PSPACE é muito maior que a classe NP, embora esta afirmativa extremamente intuitiva seja ainda hoje uma conjectura.

Concluímos esta seção com a observação seguinte. Introduzimos aqui dois novos elementos em nossa discussão. Em primeiro lugar, estamos agora admitindo que o Rei Artur tem acesso a uma fonte bits aleatórios, e, em segundo, que o nosso Rei está disposto a ser convencido de um fato através de uma conversa, ou uma interação, com Merlin. O fato surpreendente é que, com esta introdução de um elemento aleatório no processo de verificação de uma afirmativa, a classe de afirmativas verificáveis foi grandemente ampliada.

2.2. Provas verificáveis probabilisticamente. O elemento interativo da seção anterior pode ser, na verdade, eliminado ou pelo menos ‘escondido’ da seguinte forma. Lembremos que o jogo de Artur– Merlin para convencer o Rei Artur da inexistência de um circuito hamiltoniano no grafo dos seus 150 cavaleiros termina com um número polinomial de lances; em particular, o jogo sempre termina. Assim, Merlin não precisa estar presente durante o jogo: basta que ele deixe escrito em uma ‘prova’ Π como ele responderia a qualquer lance do Rei Artur. Tal prova Π precisaria ser acessada pelo Rei Artur através de um ‘oráculo’ (um súdito extremamente eficaz^{5}), já que esta prova pode ser extremamente extensa—Merlin precisa levar em conta todos os possíveis lances do Rei. Note também que apenas partes da prova Π serão examinadas pelo Rei Artur, a saber, os trechos correspondentes aos seus lances. Ademais, como o Rei Artur vai basear seus lances em bits aleatórios, ele verificará a prova Π em locais escolhidos aleatoriamente.

Temos assim um novo tipo de certificado: para Merlin convencer o Rei de que não existe uma solução para o problema do banquete pacífico, ele pode escrever uma prova Π, possivelmente bastante longa, que tem a seguinte propriedade. Caso não exista tal solução, esta prova Π convence o Rei Artur deste fato quando ela é examinada pelo Rei. Quando a tal solução existe, independentemente do que Merlin apresente como uma ‘prova’ da inexistência desta solução, o Rei Artur tem uma grande chance de descobrir que esta prova é errônea. A verificação do Rei Artur é baseada em bits aleatórios, e ele precisa de um oráculo para acessar a prova apresentada Π, já que esta prova pode ser bastante longa.

5e totalmente confiável

Note que neste novo sistema de certificados, não há interação entre as partes. Estes certificados são denominados certificados ou provas verificáveis probabilisticamente. Um resultado central neste texto é que se temos um problema de decisão e este problema pertence à classe NP, então a resposta sim a este problema pode ser certificada com uma prova verificável probabilisticamente extremamente eficiente e robusta. Tais provas são conhecidas genericamente como certificados ou provas transparentes ou holográficas.

O resultado principal sobre provas transparentes, devido a Arora, Lund, Motwani, Sudan, e Szegedy [ALM^{+}92b], pode ser informalmente enunciado como segue. Suponha que queiramos certificar a resposta sim para uma instância de tamanho n de um dado problema. Então existe uma prova verificável probabilisticamente Π que, ao ser examinada pelo Rei Artur, apenas uma quantidade não maior que uma constante independente de n de caracteres desta prova Π será lida, sendo a escolha destes caracteres baseada em apenas O(log n) bits aleatórios.

Consideremos o seguinte exemplo concreto. Suponha que o problema do banquete pacífico admite uma solução, i.e., existe um circuito hamiltoniano no grafo dos 150 cavaleiros. Então é possível se apresentar uma prova Π deste fato com a seguinte propriedade: o Rei Artur lê uma quantidade pequena de caracteres desta prova e ele escolhe a localização destes caracteres através de um número também pequeno bits aleatórios. Genericamente, se o Rei Artur tivesse n cavaleiros, um número constante de caracteres desta prova seriam examinados e seriam necessários O(log n) bits aletórios para a escolha destes caracteres. Note que, em particular, muito pouca informação seria adquirida pelo Rei Artur neste processo: a leitura de uma quantidade constante de bits da prova não pode, por exemplo, dar-lhe muita informação sobre como é a solução do seu problema do banquete pacífico. Entretanto, esta leitura será suficiente para convencê-lo de que uma solução existe.

O resultado de Arora, Lund, Motwani, Sudan, e Szegedy é um dos temas centrais deste texto.

2.3. Conseqüências para sistemas formais. O leitor não particularmente interessado em teoria de complexidade pode achar que a existência de certificados transparentes para afirmativas NP seja um resultado muito específico desta área. Discutimos brevemente nesta seção que o contexto em que este resultado se encaixa é, na verdade, extremamente amplo.

Considere, por exemplo, um sistema formal como a teoria dos conjuntos de Zermelo–Fraenkel ou a aritmética de Peano. Seja A uma afirmativa e Π uma demonstração de A dentro deste sistema formal. Temos assim um teorema e pode-se dizer que a demonstração é um certificado de pertinência de A à linguagem constituída pelos teoremas. A discussão acima pode ser aplicada neste contexto para fornecer um novo sistema formal que define o mesmo conjunto de teoremas, mas em que o processo de verificação da correção de uma demonstração é outra. Um pouco mais especificamente, a afirmativa A e a prova Π acima podem ser transformadas em uma seqüência de símbolos Π′ que, neste novo sistema formal, é uma prova de que A é um teorema. O agente que está verificando a correção da prova Π′ (o ‘Rei Artur’) deve ter acesso a O(log n) bits aleatórios e, com base nestes bits, ele precisa escolher criteriosamente os pontos da prova Π′ a serem verificados. A quantidade de pontos de Π′ efetivamente escrutinados ou, mais precisamente, o números de bits de Π′ a serem lidos pelo verificador é limitado por uma constante absoluta. Aqui n indica o comprimento total |A| + |Π| do par teorema-prova (A, Π) do qual partimos. Ademais, a obtenção da prova Π′ é algoritmicamente simples: Π′ pode ser obtida de (A, Π) através de um algoritmo polinomial.

3. Conseqüências para Problemas de Otimização

3.1. Problemas NP-difíceis. No início dos anos 70 uma descoberta atingiu fundo a teoria da computação. Constatou-se que um certo grupo bastante amplo de problemas importantes e aparentemente

3. CONSEQÜÊNCIAS PARA PROBLEMAS DE OTIMIZAÇÃO 11

difíceis do ponto vista computacional eram equivalentes no seguinte sentido: caso existisse um algoritmo eficiente para resolver qualquer um desses problemas, existiriam algoritmos eficientes para resolver todos os outros problemas. Estes problemas são ditos serem NP-difíceis, e incluem problemas das mais variadas áreas, como projetar redes telefônicas ou rotas de aviões, seqüenciar tarefas numa fábrica, encontrar soluções inteiras para equações quadráticas do tipo ax^{2} + by = c, determinar o permanente de matrizes de 0s e 1s, encontrar soluções inteiras para problemas de programação linear, dentre muitos outros. Como um grande número de pesquisadores já haviam tentado resolver separadamente vários desses problemas,^{6} a comunidade passou a acreditar na impossibilidade da obtenção de algoritmos eficientes para os problemas nesse grupo. Esta crença tornou-se a bem conhecida conjectura P ≠ NP, que é central em teoria da computação.^{7}

Surpreendentemente, o fato de asserções em NP terem certificados probabilisticamente verificáveis extremamente eficientes e robustos implica que encontrar soluções aproximadas para uma ampla gama de problemas de otimização é tão difícil quanto encontrar uma solução exata. Esse fato, que veio a público em 1992, teve impacto semelhante ao descrito no parágrafo anterior. Pesquisadores que tentavam ‘ingenuamente’ encontrar soluções aproximadas para problemas considerados difíceis, tiveram que mudar o rumo de suas pesquisas da noite para o dia em face desses resultados.

3.2. O problema do clique máximo. O primeiro problema para o qual se provou a impossiblidade de aproximações em vista desta nova teoria foi o problema do clique máximo. Suponha que temos um grafo G e que queremos encontrar o maior inteiro k tal que G contém um subgrafo completo de ordem k, isto é, um clique de ordem k. Em outras palavras, queremos saber o maior k para o qual temos em G um conjunto de k vértices dois-a-dois adjacentes. Escreva ω(G) para este k. Os resultados obtidos nos anos 70 mostram que a determinação exata de ω(G) para um dado grafo G é um problema NP-difícil. Uma pergunta natural é então a seguinte: é mais fácil obter uma estimativa de ω(G)?

6Um problema comprovadamente não mais difícil é o de fatorar eficientemente números inteiros. Babai [Bab94] observa que Fermat e Gauss provavelmente teriam adorado conhecer uma solução deste problema.

7Em correspondência descoberta recentemente, Gödel escreve a von Neumann levantando a questão sobre a relação entre P e NP, não descartando a possibilidade de que P = NP, e observa que este resultado teria conseqüências profundas; veja Sipser [Sip92].

Infelizmente, o resultado aqui é negativo: existe uma relação um tanto inesperada entre este problema e certificados transparentes, e esta relação fornece, como um corolário do teorema de Arora, Lund, Motwani, Sudan, e Szegedy, o seguinte resultado. Existe uma constante absoluta ε > 0 tal que se existe um algoritmo polinomial para estimar ω(G) a menos de um fator multiplicativo de n^{ε}, então existe um algoritmo polinomial para determinar o valor exato de ω(G).

Salientamos que o resultado acima não é de forma alguma um resultado isolado. Como mencionado acima, conhece-se hoje uma ampla classe de problemas que não admitem algoritmos de aproximação eficientes, a menos que P = NP e que desta forma todos eles possam ser resolvidos exatamente.

4. A Organização deste Texto

Este texto tem basicamente duas partes: a primeira delas tem o objetivo de introduzir o leitor aos resultados recentes da teoria da complexidade que culminaram com o resultado de Arora, Lund, Motwani, Sudan, e Szegedy. Esta parte tem dois capítulos. No Capítulo III discutimos provas interativas, inclusive provando o resultado IP = PSPACE discutido acima. Dedicamos todo o Capítulo IV às provas verificáveis probabilisticamente. Discutimos neste capítulo várias das idéias envolvidas na demonstração do resultado de Arora et al., em particular, provando inteiramente um resultado intermediário que afirma que qualquer afirmativa NP admite um certificado cuja correção pode ser verificada pelo Rei Artur através do escrutínio de uma quantidade constante de seus caracteres, desde que ele tenha acesso a uma quantidade polinomial, e não apenas logarítmica, de bits aleatórios.

A segunda parte deste texto, constituída pelo Capítulo V, é dedicada às conseqüências do resultado de Arora et al. à área de otimização combinatória. Em particular, veremos como deduzir o resultado negativo relativo ao problema do clique máximo discutido na Seção 3.2.

O Capítulo II contém uma discussão sucinta das bases formais em que a teoria da complexidade computacional se fundamenta. O Apêndice A contém as definições dos problemas que são mencionados no decorrer do texto. O Apêndice B contém a terminologia e os conceitos básicos.

5. Notas Bibliográficas

Parte deste capítulo, incluindo a fábula do Rei Artur e Merlin, segue de perto Babai [Bab90]. Outro trabalho que fornece uma ótima introdução aos tópicos discutidos acima é Babai [Bab94]; em particular, o enfoque brevemente discutido na Seção 2.3 é elaborado detalhadamente neste trabalho. O fato de que provas interativas podem certificar a negativa de asserções NP foi provado por Lund, Fortnow, Karloff, e Nisan [LFKN92]; em realidade, o resultado destes autores é muito mais forte: eles provaram que P^{#P} ⊂ IP (veja o Capítulo III para as definições). O resultado de que IP = PSPACE é devido a Shamir [Sha92], que segue de perto [LFKN92].

O resultado principal sobre provas transparentes é devido a Arora, Lund, Motwani, Sudan, e Szegedy [ALM^{+}92b], embora muitas das idéias contidas neste trabalho tenham origem em Arora e Safra [AS92b]. Além dos trabalhos originais de Arora et al. [ALM^{+}92a, ALM^{+}92b], Sudan [Sud92], Arora [Aro94], e Hougardy, Prömel, e Steger [HPS94] apresentam demonstrações do resultado central sobre provas transparentes. Estes trabalhos também discutem as conseqüências deste resultado no estudo de problemas de aproximação.

A teoria de complexidade clássica nasceu oficialmente com os trabalhos de Cook [Coo71], Karp [Kar72], e Levin [Lev72] (uma tradução deste último trabalho aparece em Trakhtenbrot [Tra84]). A referência básica é Garey e Johnson [GJ79]. A noção de boas caracterizações de Edmonds aparece em [Edm65a]; veja também Edmonds [Edm65b], que apresenta uma das primeiras discussões específicas sobre a noção de eficiência de um algoritmo como entendemos hoje. Para uma discussão muito interessante sobre o nascimento e a situação atual da conjectura P ≠ NP, veja Sipser [Sip92]. Este trabalho contém também uma tradução da carta de Gödel a von Neumann.

14 I. INTRODUÇÃO

CAPÍTULO II PRELIMINARES

O objetivo deste capítulo é o de introduzir alguns conceitos básicos e resultados clássicos que serão usados nestas notas. Damos uma noção do modelo computacional a ser usado e definições das principais classes de complexidade computacional. Terminamos o capítulo tecendo alguns comentários sobre linguagens recursivas com o intuito de facilitar a leitura para o leitor familiarizado com esses conceitos.

1. Modelos Computacionais

A análise de recursos computacionais envolvidos para se resolver problemas pelo computador é o objeto de estudo da Teoria da Complexidade. Para tanto faz-se necessário estabelecer modelos computacionais abstratos que exprimam os aspectos práticos de uma computação.

O principal modelo usado nestas notas é o da máquina de Turing. Não iremos definir o que é uma máquina de Turing. Essa definição requer uma carga de formalismo grande que não ajuda muito no entendimento do que se pode ou não computar com uma máquina de Turing. Para o leitor não familiarizado com esse modelo computacional, tentaremos dar uma idéia geral do que ele vem a ser.

Comentamos inicialmente que, embora a máquina de Turing venha a ser um modelo ‘primitivo’ de computação, é amplamente aceita a Tese de Church, segundo a qual qualquer procedimento pode ser programado numa máquina de Turing. Não existe uma definição precisa de procedimento, o que impede, é claro, que a Tese de Church jamais venha a ser provada. Como noção informal, um procedimento é uma seqüência finita de instruções que pode ser executada por um agente computacional.

1.1. Tempo e espaço. Quanto aos recursos computacionais envolvidos, estamos interessados principalmente em duas medidas: o tempo e o espaço. O tempo de processamento de uma computação numa máquina de Turing é o número de passos executados até a término da computação. O espaço usado é a quantidade de bits ou células de memórias usadas na computação.

Fixando-se um problema P, é natural que o tempo e espaço de processamento variem de acordo com a instância do problema considerado. Por exemplo, considere o problema da primalidade, ou seja, decidir se um dado número é primo. É de se esperar que o tempo e espaço usados por um algoritmo que resolva este problema cresçam com o tamanho do número a ser analisado. Dessa forma, o tempo e espaço são expressos em função do tamanho da entrada ou instância do problema. O tamanho de uma instância x, ou o tamanho de uma entrada x, de um problema P é o número de símbolos usados na descrição de x obtido por um esquema de codificação. Esse tamanho será denotado por |x|.

Um esquema de codificação é uma forma ‘conveniente’ de mapear instâncias de um problema em seqüências de caracteres. Para estabelecer um esquema de codificação precisamos inicialmente escolher um conjunto finito de caracteres Σ que será usado na descrição das instâncias do problema. Por exemplo, no caso da primalidade, um esquema de codificação para uma instância do problema poderia ser simplesmente a representação decimal de n. Portanto, o nosso alfabeto seria {0, 1, …, 9}.

A complexidade em tempo (resp., espaço) de um algoritmo que resolve um problema P é uma função do tamanho da entrada que expressa, para cada possível tamanho de entrada, a maior quantidade de tempo (resp., espaço) requerido pelo algoritmo para resolver uma instância daquele tamanho. É claro que essas complexidades dependem do modelo computacional adotado. Essas medidas, porém, não são alteradas substancialmente se o modelo adotado for realista.

1.2. Máquinas de Turing e RAM. Para dar uma idéia concreta do que é uma máquina de Turing, faremos um paralelo entre este modelo e programas de computadores reais. Uma boa aproximação, em termos computacionais de um computador são as Máquinas de Acesso Aleatório (RAM — Random Access Machines). Uma máquina RAM, para todos os efeitos, é uma máquina capaz de executar programas exatamente como os computadores existentes. A principal diferença é que qualquer computador real tem capacidade de armazenamento limitada, enquanto que no modelo RAM essa limitação não existe.

O seguinte fato mostra uma eqüivalência entre os modelos RAM e máquinas de Turing.

Teorema 1. O modelo RAM, sob o critério de custos logarítmico, e o modelo de máquina de Turing são modelos relacionados polinomialmente.

Explicamos a seguir o significado dos termos usados. O critério de custos logarítmico considera o tempo de execução de instruções proporcional ao comprimento em bits dos operandos. Dizemos que duas funções f(n) e g(n) são relacionadas polinomialmente se existirem polinômios p_{1}(x) e p_{2}(x) tais que, para todo n, temos f_{1}(n) ≤ p_{1}(f_{2}(n)) e f_{2}(n) ≤ p_{2}(f_{1}(n)). Dois modelos computacionais são relacionadas polinomialmente se qualquer algoritmo implementado em um modelo pode ser simulado por um outro algoritmo no segundo modelo de forma que as complexidades dos algoritmos são relacionadas polinomialmente.

Assim, o leitor não familiarizado com máquinas de Turing pode imaginar que uma máquina de Turing é um programa de um computador com capacidade de armazenamento ilimitada e onde os custos das operações levam em conta os tamanhos em bits dos operandos. Quando usamos a expressão ‘seja M uma máquina de Turing,’ O paralelo que deve ser feito é que um programa de um computador é dado. Ou seja, uma máquina de Turing corresponde a um programa escrito de acordo com o modelo geral das máquinas de Turing.

Os dados de entrada para um máquina de Turing M são fornecidos numa fita de entrada na qual M faz as leituras. O resultado da computação de M é escrito numa fita de saída.

2. As Classes P e NP

Os problemas classificados nas classes P e NP são problemas de decisão, ou seja, problemas cuja resposta é sim ou não. O intuito dessa restrição aos problemas de decisão é o de permitir o uso de conceitos e ferramentas envolvidos no formalismo das linguagens formais.

Fixe um conjunto finito Σ, chamado de alfabeto. O conjunto de todas as seqüências finitas de elementos de Σ, chamadas de palavras, é denotado por Σ^{∗}. O tamanho de uma palavra x ∈ Σ^{∗}, isto é, o número de símbolos usados para se escrever x, é denotado por |x|. Uma linguagem L sobre o alfabeto Σ é qualquer subconjunto L ⊆ Σ^{∗}. O complemento de L, denotado por \overline{L}, é definido por \overline{L} = Σ^{∗} \ L. Fixando uma linguagem L ⊆ Σ^{∗}, o problema da pertinência é: dado um x ∈ Σ^{∗}, decidir se x ∈ L.

Com esse formalismo, os problemas de decisão nada mais são do que problemas de pertinência em linguagens ou conjuntos. Considere um problema de decisão P com um esquema de codificação sobre um alfabeto Σ. Considere a linguagem L sobre Σ definida por

L = {x: x é uma codificação de uma instância de P cuja resposta é sim}.

Decidir pertinência em L é o mesmo que decidir sobre a resposta ao problema de decisão P. Por exemplo, considere o problema da primalidade. Seja L a linguagem consistindo das palavras sobre o alfabeto Σ = {0, 1, …, 9} que representam, em notação decimal, números primos. O problema de decisão correspondente, Primalidade, é: dado uma palavra x ∈ Σ^{∗}, decidir se x ∈ L.

Dizemos que uma máquina de Turing M reconhece uma linguagem L se M resolve o problema de pertinência para L. Ou seja, para todo x ∈ Σ^{∗}, se x é escrito na fita de entrada de M, depois de um número finito de passos M pára escrevendo sim na fita de saída se x ∈ L, e escrevendo não caso contrário.

Em geral trabalhamos com alfabetos com pelo menos dois símbolos. Não perdemos muito se considerarmos que o nosso alfabeto é sempre o alfabeto binário {0, 1}. Qualquer linguagem sobre um alfabeto finito Σ pode ser convenientemente codificada em binário, de forma que qualquer palavra x ∈ Σ^{∗} tem tamanho no alfabeto binário no máximo |x|(1 + log_{2} |Σ|), ou seja, o tamanho das palavras diferem somente de um fator constante, uma vez que |Σ| é constante.

As medidas de complexidade de tempo e espaço são dadas em função do tamanho de x, a entrada do problema. Para uma função t(n), uma máquina de Turing M é dita ter complexidade de tempo t(n) se para qualquer n e para qualquer entrada x ∈ Σ^{∗} de comprimento n, a máquina M pára depois de O(t(n)) passos. O conjunto das máquinas de Turing limitadas polinomialmente consiste da união, para todo k > 0, das máquinas de Turing com complexidade de tempo n^{k}. A máquina de Turing M é dita ter complexidade de espaço t(n) se a maior quantidade de memória usada por M em suas computações é no máximo O(t(n)). Aqui, cada unidade de memória armazena um símbolo de Σ.

Uma máquina de Turing que, para qualquer entrada, pára após um número finito de passos é chamada de algoritmo. Um algoritmo polinomial é uma máquina de Turing limitada polinomialmente. Dizemos que uma função f: X → Y é computável em tempo polinomial, ou simplesmente, que f é uma função polinomial, se, existe um algoritmo polinomial que, para todo x ∈ X, calcula o valor f(x).

2.1. Sistemas de provas. Um sistema de provas consiste de duas máquinas de Turing: V, o verificador, e P, o provador, que se comunicam. As duas máquinas de Turing têm acesso comum a uma fita de leitura contendo uma palavra x. Iremos impor restrições ao poder computacional da máquina V, mas P sempre terá poder computacional ilimitado. Existem ainda mais duas fitas, F_{P} e F_{V}, compartilhadas por V e P. Numa delas, na fita F_{P}, o provador P pode escrever e V somente fazer leituras. Na outra delas, na fita F_{V}, os papéis são trocados, ou seja, V pode escrever e P somente fazer leituras. Veja Figura II.1.

2.2. A classe P. Definimos aqui a classe de linguagens que, em teoria, correspondem a problemas de decisão algoritmicamente tratáveis, isto é, problemas para os quais soluções computacionais são viáveis.

Definição 2. Uma linguagem L ⊆ Σ^{∗} está na classe de linguagens DTIME(t(n)) (Deterministic TIME) se existe um sistema de provas tal que para todo x ∈ Σ^{∗}, com n = |x|,

(1) a máquina de Turing V tem complexidade de tempo t(n);

[figure: Verificador; Escrita; Leitura; Leitura; Leitura; Leitura; Fita F_{P}; Fita F_{V}; Escrita; Provador; P; V; Fita de Entrada]

Figura II.1. Sistema de Provas

(2) se x ∈ L a máquina de Turing V, no término de suas computações, escreve sim na fita F_{V} sem nunca consultar a fita F_{P}; neste caso dizemos que V aceita x.

(3) se x ∉ L a máquina de Turing V, no término de suas computações, escreve não na fita F_{V} sem nunca consultar a fita F_{P}; neste caso dizemos que V rejeita x.

Note que, nessa definição, o provador P e a fita F_{P} não têm nenhuma importância. Tudo depende somente da máquina de Turing V cuja complexidade de tempo é limitada por t(n).

Definição 3. A classe P (tempo polinomial) é definida por

P = ⋃_{k>0} DTIME(n^{k}),

e a classe EXP (tempo exponencial) é definida por

EXP = ⋃_{k>0} DTIME(2^{n^{k}}).

2.3. A classe NP. A classe de linguagens definida a seguir contém a classe P e, intuitivamente, corresponde às linguagens que admitem certificados de pertinência simples.

Definição 4. Uma linguagem L ⊆ Σ^{∗} está na classe de linguagens NTIME(t(n)) (Non-Deterministic TIME) se existe um sistema de provas tal que para todo x ∈ Σ^{∗}, com n = |x|,

(1) a máquina de Turing V tem complexidade de tempo t(n);

(2) P computa uma palavra y e a escreve na fita F_{P};

(3) se x ∈ L a máquina de Turing V, no término de suas computações, escreve sim na fita F_{V} após eventuais consultas à fita F_{P};

(4) se x ∉ L a máquina de Turing V, no término de suas computações, escreve não na fita F_{V} após eventuais consultas à fita F_{P}.

Definição 5. A classe NP (tempo polinomial não-determinístico) é definida por

NP = ⋃_{k>0} NTIME(n^{k}),

e a classe NEXP (tempo exponencial não-determinístico) é definida por

NEXP = ⋃_{k>0} NTIME(2^{n^{k}}).

O sistema de provas para uma linguagem em NP é chamado de sistema NP de provas.

A definição da classe NP nos diz que se uma linguagem L ∈ NP então para todo x ∈ L existe uma prova y, fornecida pelo provador, de que x ∈ L. Ademais, esta prova y pode ser verificada em tempo polinomial em |x|. Por exemplo, para provar que um número inteiro n é composto, basta exibir um de seus divisores d. A verificação de que de fato d | n pode ser feita em tempo polinomial no número de dígitos de n. De maneira formal, uma linguagem L está na classe NP se existe um c > 0 e existe L_{1} ∈ P tais que

(∀x ∈ Σ^{∗})(x ∈ L ⇔ (∃y)(|y| ≤ |x|^{c} e (x, y) ∈ L_{1})).

Nestes termos, x é a entrada e y é a prova de que x ∈ L, ou um certificado da pertinência de x a L.

Abusando da linguagem, vamos dizer que ‘um problema de decisão P está na classe de complexidade X’ quando existir um esquema de codifição para P tal que a linguagem L definida pela codificação das instâncias de P que têm resposta sim está em X.

Na definição da classe NP não podemos trocar o papel da resposta sim pela resposta não. Por exemplo, enquanto trivialmente existe uma prova curta de que um número é composto (basta exibir um divisor próprio do número) a situação é menos clara para se provar que um número é primo.^{1} Portanto, é imediato concluir que o problema de decidir se um dado número é composto está em NP, enquanto que não é imediato que o problema de decisão Primalidade ∈ NP. Um outro exemplo é o do Problema Circuito Hamiltoniano. Para provar que um grafo tem um circuito hamiltoniano, basta exibir um tal circuito. Por outro lado não se conhecem provas ‘curtas’ de que um dado grafo não é hamiltoniano. Em outras palavras, não se sabe se o problema de decidir se um grafo não é hamiltoniano está em NP.

Pelos comentários acima, faz sentido definirmos a classe de problemas complementares aos problemas em NP, a classe coNP. A classe de linguagens coNP é definida por

coNP = {Σ^{∗} \ L : L ⊆ Σ^{∗} e L ∈ NP}.

O maior problema em aberto em Ciência da Computação é se P é diferente de NP. Em outros termos, verificar uma prova é computacionalmente mais fácil do que encontrá-la [LSS^{+}77]? Muitas evidências indicam que P ≠ NP. Outra conjectura é que NP ≠ coNP. Das definições acima é fácil concluir que P ⊆ NP ∩ coNP, e a conjectura é que a inclusão é própria. Também é fácil de ver que P é fechada sobre complementação, isto é, P = coP. Portanto, NP ≠ coNP implica que P ≠ NP, embora NP = coNP não implique que P = NP.

2.4. A classe PSPACE. Mencionamos por último que as classes de complexidade relativas ao espaço usado pelas computações são definidas de maneira análoga, trocando-se, nas definições, complexidade de tempo por complexidade de espaço. Uma classe que iremos usar é a classe PSPACE, definida por

1Embora exista também, para todo número primo, uma prova curta de sua primalidade [Pra75].

PSPACE = ⋃_{k>0} DSPACE(n^{k}).

Veja que neste caso não há limitação em relação ao tempo de processamento. Não é muito difícil de ver que NP ⊆ PSPACE. Para tanto, suponha que exista um sistema NP de provas com provador P e verificador V para uma linguagem L. Podemos, baseado nesse sistema, contruir um sistema de provas que caracterize a pertinência de L em PSPACE. Para cada entrada x, um novo verificador V′ simula, para cada possível conteúdo y da fita F_{P}, a computação de V. (Lembre que y tem comprimento polinomial em |x|.) O verificador V′ pára com resposta sim se e somente se para algum dos y o verificador V pára com resposta sim. Como o tempo usado por V é polinomial em |x|, é claro que V′ usa espaço polinomial para cada uma das simulações.

Embora PSPACE contenha também coNP e várias outras classes, não se sabe nem mesmo se P ≠ PSPACE.

3. Problemas de Enumeração e a Classe #P

Nos problemas de decisão estamos interessados em saber se uma determinada instância de um problema tem ou não uma certa propriedade. Por exemplo, dado um grafo, queremos saber se ele tem um circuito hamiltoniano. Um problema de enumeração consiste em contarmos quantas soluções um problema tem. No caso do Circuito Hamiltoniano, o problema de enumeração é saber quantos circuitos hamiltonianos distintos um grafo tem (eventualmente esse número é zero).

Mais formalmente, um problema de enumeração P consiste de um conjunto I de instâncias para P e, para cada x ∈ I, um conjunto finito S(x) de soluções para x. A solução do problema de enumeração é a cardinalidade de S(x). Se P é o Problema Circuito Hamiltoniano, o conjunto I consiste de todos os grafos finitos e para cada grafo x ∈ I, o conjunto S(x) é constituído por todos os circuitos hamiltonianos do grafo x.

Um problema de enumeração P está na classe #P se existe um sistema NP (veja Definição 5) de provas tal que para cada instância x de P, o número dos y fornecidos pelo provador que levam o verificador a aceitar x é igual à cardinalidade de S(x). Abusando da notação, dizemos que uma função f: Σ^{∗} → ℕ está em #P se o valor de f, para cada x, é o número dos y que levam o verificador a aceitar x.

4. Linguagens Recursivas

A leitura desta seção não é essencial para o entendimento do restante dos capítulos. Nosso objetivo aqui é esclarecer, para o leitor familiarizado com o conceito de funções recursivas, alguns pontos que possam ter ficados obscuros neste capítulo.

Seja Σ um alfabeto finito. Uma função f: Σ^{∗} → Σ^{∗} é recursiva ou computável se existe uma máquina de Turing que para qualquer entrada x ∈ Σ^{∗} calcula f(x) após um número finito de passos.

Uma linguagem L é recursiva se sua função característica f_{L}, definida sobre Σ^{∗} e dada por

f_{L}(x) = \begin{cases}1 & se x ∈ L \\ 0 & caso contrário, \end{cases}

é recursiva. Ou seja, se existe uma máquina de Turing T que resolve o problema de pertinência para L. Neste caso dizemos que T decide L, ou que L é decidível. Uma linguagem L que não é recursiva, ou seja, L não é decidível, é dita ser indecidível.

Pelas definições acima, dizer que uma linguagem L é indecidível é equivalente a dizer que não existe uma máquina de Turing capaz de decidir o problema de pertinência para L. Pela Tese de Church isso quer dizer que não existe um procedimento efetivo para decidir pertinência em L.

A ‘maior’ classe definida na seção anterior é a classe NEXP. Destacamos aqui que, embora NEXP contenha linguagens que são consideradas computacionalmente intratáveis (acredita-se que este já é o caso para algumas linguagens em NP), é óbvio que a classe NEXP está contida na classe de linguagens recursivas. Ou seja, embora possamos considerar as linguagens em NEXP fáceis de serem computadas por serem linguagens recursivas, a estória é outra quando consideramos os recursos computacionais envolvidos nessa computação.

Veremos a seguir classes de linguagens que contém propriamente a classe de linguagens recursivas. Uma linguagem L é recursivamente enumerável se L = ∅ ou existe uma função recursiva f tal que a imagem de f é L. Ou seja, podemos enumerar os elementos de L: L = {f(w_{0}), f(w_{1}), … }, se Σ^{∗} = {w_{0}, w_{1}, … }.

Uma definição alternativa de linguagens recursivamente enumeráveis é dada pelo seguinte lema.

Lema 6. Uma linguagem L é recursivamente enumerável se e somente se existe uma máquina de Turing que com entrada x pára se e somente se x ∈ L.

É um fato bem conhecido que se L é recursiva, o seu complemento \overline{L} = Σ^{∗} \L também é. E que se L e \overline{L} são recursivamente enumeráveis, então L é recursiva.

4.1. O problema da parada. Vamos mostrar a seguir uma linguagem que é recursivamente enumerável mas não recursiva.

Seja T uma máquina de Turing. O problema da parada para T é decidir, para todas as possíveis entradas x, se T com entrada x pára. Seja L = {⟨T, x⟩: T com entrada x pára}. Aqui, T deve ser entendido como uma codificação conveniente da máquina de Turing T. O seguinte teorema é bastante conhecido.

Teorema 7. A linguagem L é recursivamente enumerável mas não recursiva.

Em outras palavras, o problema da parada é computacionalmente indecidível. Ou seja, como comentado na Introdução, o problema da parada não pode ser resolvido por processos algorítmicos.

Segue também que, pelo exposto acima, o complemento de L não é recursivamente enumerável. Embora esse exemplo de linguagem não recursiva possa parecer não muito natural, existem muitos outros problemas que são também indecidíveis. De fato, considere o seguinte problema.

Problema 8. Dado um polinômio p(x_{1}, x_{2}, …, x_{n}) com coeficientes inteiros e n variáveis, decidir se a equação p = 0 tem uma solução inteira.

A indecidibilidade do problema acima foi provada por Matiyasevich em 1970, resolvendo assim o Décimo Problema de Hilbert. (Veja, por exemplo, Matiyasevich [Mat93].)

5. Notas Bibliográficas

As máquinas de Turing foram formalizadas por Alan Turing [Tur36]. O Teorema 1 é devido a Cook e Reckhow [CR73]. Para uma introdução mais detalhada às classes de complexidade descritas neste capítulo, veja Garey e Jonhson [GJ79].

A classe #P foi definida de maneira similar por Valiant [Val79] e Janos Simon [Sim75].

CAPÍTULO III PROVAS INTERATIVAS

Num sistema de provas interativo temos um ser todo-poderoso, o Mago Merlin, e um humano comum, o Rei Artur. Suponha que Merlin queira convencer o desconfiado Rei Artur de que uma palavra x pertence a uma linguagem L. Embora o Rei seja bastante inteligente, dispõe somente de tempo polinomial para ser convencido de que x ∈ L. Quais são as classes de linguagens para as quais Merlin está apto a convencer o Rei Artur da resposta afirmativa ao problema de pertinência? Suponha que o Rei não se incomode em ser 100% convencido que x ∈ L, mas se tiver, digamos, 99% de certeza se dará por convencido. Será que com essas condições Merlin pode convencer o Rei da resposta sim ao problema de pertinência para uma classe grande de linguagens?

Se exigimos que o Rei Artur seja 100% convencido, a resposta é que, para todo x ∈ L, o Rei pode ser convencido de que x ∈ L se e somente se L ∈ NP. A razão disso é que, primeiro, no sistema de provas que define NP, Merlin faria o papel do Provador P e o Rei Artur do Verificador V. E em segundo lugar, uma prova interativa totalmente determinística pode ser facilmente simulada por um sistema NP de provas. Por outro lado, se 99% de certeza for o suficiente, a resposta é surpreendente: para todo x ∈ L, o Rei pode ser convencido de que x ∈ L se e somente se L ∈ PSPACE. Como já mencionamos na Introdução, acredita-se que PSPACE seja uma classe de linguagens muito maior que NP.

1. Definições e Modelos

Informalmente, um sistema de provas interativo consiste de um jogo entre um Provador P (‘Merlin’) e um Verificador V (‘Rei Artur’). Dado uma linguagem L ⊆ Σ^{∗} e um x ∈ Σ^{∗}, a tarefa de Merlin é convencer o Rei Artur de que x ∈ L. Merlin nem sempre é honesto (nem sempre x ∈ L) e o honesto Rei Artur precisa ter uma estratégia para não se deixar enganar. O Rei tem acesso a bits aleatórios. O que ele precisa fazer é, baseado na entrada x e eventualmente consultando bits aleatórios, interagir com Merlin para se certificar que x ∈ L. De acordo com as respostas de Merlin, o Rei pode querer fazer mais perguntas, usando ou não mais bits aleatórios. Como Merlin é todopoderoso, ele não gasta tempo nenhum para dar suas repostas. Assim, o processo todo fica limitado somente pelo Rei Artur, cujo tempo total para fazer suas computações é limitado polinomialmente. Dizemos que a linguagem L ∈ IP se para qualquer x ∈ L Merlin consegue convencer o Rei disso, e para qualquer x ∉ L, qualquer que seja a estratégia de Merlin, a probabilidade do Rei ser convencido de que x ∈ L é muito pequena. Convencionamos dizer que Merlin ganha o jogo se o Rei Artur se convence de que x ∈ L. Caso contrário, Merlin perde.

Um sistema de provas interativo consiste de duas máquinas de Turing: o verificador V e o provador P que se comunicam. As duas máquinas de Turing têm acesso comum a uma fita de leitura contendo uma palavra x. A máquina de Turing V é limitada polinomialmente e tem acesso a uma fita contendo bits aleatórios. A máquina de Turing P tem poder computacional ilimitado. Existem ainda mais duas fitas, F_{P} e F_{V}, compartilhadas por V e P. Numa delas, na fita F_{P}, o provador P pode escrever e V somente fazer leituras. Na outra delas, na fita F_{V}, os papéis são trocados, ou seja, V pode escrever e P somente fazer leituras. Usando essas fitas, P e V interagem trocando mensagens. Veja Figura III.2.

Um ‘detalhe’ não comentado até agora é se Merlin pode ‘ver’ os bits aleatórios do Rei Artur na medida em que este acessa esses bits. Esse detalhe, que conforme veremos não é tão importante, deu origem à definição de duas classes de complexidade em provas interativas, as classes IP e AM, que definiremos a seguir.

[figure: Verificador; Escrita; Fita F_{P}; Fita F_{V}; Escrita; Provador; P; V; Fita de Entrada; Leitura; Leitura; Leitura; Leitura; Leitura; Fita de bits aleatórios; Merlin; Rei Artur]

Figura III.2. Sistema de Provas Interativo

1.1. As classes IP e AM. Para facilidade de leitura (e por já termos uma certa familiaridade com sua majestade o Rei Artur), chamaremos sempre de Artur a máquina de Turing V limitada polinomialmente e de Merlin a máquina de Turing P com poder computacional ilimitado. Uma linguagem L está na classe IP(t(n)) se existe um sistema de provas interativo e uma função t(n) que, para uma entrada comum x, de comprimento |x| = n, as seguintes condições são satisfeitas:

(1) Artur e Merlin trocam no máximo t(n) mensagens usando as fitas F_{P} e F_{V};

(2) para todo x ∈ L, Merlin sempre tem uma estratégia ganhadora, isto é, existe um P tal que Artur aceita a prova de P terminando suas computações escrevendo sim na fita F_{V} (esse uso da fita não faz parte das t(n) mensagens trocadas). Ou seja, Merlin sempre pode convencer o Verificador de que x ∈ L se isso for verdade.

(3) para todo x ∉ L, para qualquer Provador P, Artur rejeita a prova de P terminando suas computações escrevendo não na fita F_{V} com probabilidade ≥ 3/4. Ou seja, por mais que Merlin tente enganar Artur, a probabilidade deste ser enganado é no máximo 1/4. Essa probabilidade é medida em relação aos bits aleatórios consultados por Artur.

(4) Artur é o primeiro a fazer uso de sua fita de mensagens.

(5) Merlin não tem acesso aos bits aleatórios consultados por Ar-

tur. Quando Artur termina o protocolo escrevendo sim em sua fita, dizemos que Artur aceita [a prova de Merlin]. Caso contrário, dizemos que Artur rejeita. A classe de linguagens AM(t(n)) é definida de maneira análoga, exceto pelo item 5, onde agora Merlin e Artur têm acesso simultâneo aos bits aleatórios. O valor 3/4 colocado na definição é arbitrário e poderia ser qualquer constante estritamente entre 0 e 1. Se repetirmos de forma independente e em paralelo o sistema acima um número conveniente (constante) de vezes, podemos amplificar arbitrariamente o grau de certeza da resposta, sem aumentar o número de lances no jogo.

As classes IP e AM são definidas por

IP = ⋃_{k≥0} IP(n^{k})  e  AM = ⋃_{k≥0} AM(n^{k}).

As definições acima correspondem simplesmente a não limitar o número de mensagens trocadas entre P e V, porém mantendo-se a restrição de polinomialidade de V.

Uma variante da classe AM é a classe MA: agora quem usa a fita de mensagens primeiro é Merlin.

1.2. Um exemplo de um sistema de prova interativo. É fácil ver que NP ⊆ IP(2). Se uma linguagem L está em NP, então existe um sistema de provas para L, conforme Definição 5. Esse sistema de provas pode ser simulado por um sistema de provas interativo considerando-se que Artur abre mão de sua primeira mensagem.

Vamos mostrar nesta seção que um certo problema que não se sabe se está em NP está em IP(2). Trata-se do Problema Grafo Não-Isomorfismo, que consiste em decidir se dois grafos dados não são isomorfos.

Teorema 9. Grafo Não-Isomorfismo está em IP(2).

Prova. Seja (G_{1}, G_{2}) uma instância do problema, onde os grafos dados são G_{1} = (V, E_{1}) e G_{2} = (V, E_{2}). O protocolo entre Artur e Merlin está descrito na Figura III.3.

(1) Artur escolhe aleatoriamente c ∈ {1, 2} e uma permutação aleatória π de V.

(2) Artur computa o grafo π(G_{c}) = G_{3} = (V, E_{3}), onde E_{3} é definido por {π(u), π(v)} ∈ E_{3} se e somente se {u, v} ∈ G_{c}.

(3) Artur descreve G_{3} na fita F_{V};

(4) Merlin, depois de ler G_{3}, escreve na fita F_{P} o valor de c.

(5) Se Merlin erra no Passo 4 o valor de c, Artur rejeita; caso contrário, Artur aceita.

Figura III.3. Protocolo para Grafo Não-Isomorfismo

Se os grafos G_{1} e G_{2} não são isomorfos, então Merlin pode sempre distinguir o caso em que G_{3} é isomorfo a G_{1} do caso em que G_{3} é isomorfo a G_{2}, e sempre pode acertar no Passo 4.

Por outro lado, se G_{1} e G_{2} são isomorfos, então devido à escolha aleatória da permutação π, a probabilidade de G_{3} ser π(G_{1}) é igual à probabilidade de ser π(G_{2}). Neste caso, Merlin, desconhecendo o valor de c, irá errar no Passo 4 com probabilidade 1/2. Para obtermos o limitante desejado de 3/4 na probabilidade de acerto de Artur, o protocolo acima deve ser repetido em paralelo 2 vezes. □

No protocolo acima, é fundamental o fato de Merlin não ter acesso aos bits aleatórios de Artur, ou mais precisamente, aos valores de c e π. Porém, veremos a seguir que tal fato não é tão importante quanto parece.

1.3. Propriedades das classes IP e AM. Vamos mencionar, sem provas, duas propriedades importantes das classes IP e AM.

A primeira delas esclarece uma questão mencionada anteriormente, a saber, o quão importante é o fato de Merlin ter ou não acesso aos bits aleatórios de Artur.

Teorema 10. Para todo polinômio Q(n), temos

IP(Q(n)) ⊆ AM(Q(n) + 2).

A segunda propriedade responde a seguinte pergunta. Será que o número de vezes que Artur e Merlin trocam mensagens é relevante na definição dessas classes? A resposta a essa pergunta é um tanto surpreendente.

Teorema 11. Seja t: ℕ → ℕ uma função com t(n) ≥ 2 para todo n. Então AM(t(n)) = AM(2t(n)).

Em particular, esse teorema nos diz que a hierarquia das classes AM(k), para k finito, colapsa. Ou seja, AM(2) = AM(k) para qualquer inteiro k. Note que o teorema não implica que a classe AM, na qual não se limita o número de trocas de mensagens, colapse. Pelo Teorema 10, os mesmos comentários se aplicam à classe IP.

2. coNP ⊂ IP

Provaremos nesta seção que se uma linguagem L admite certificados polinomiais de pertinência, então a afirmativa x ∉ L admite uma prova interativa. Formalmente, coNP ⊂ IP. Na próxima seção provaremos algo muito mais forte, a saber, que PSPACE ⊂ IP. A presente seção é mais um aquecimento para que possamos adquirir maior familiaridade com provas interativas, e também para ver um dos componentes da demonstração de que PSPACE ⊂ IP, a saber, o ‘Protocolo lfkn’ de Lund, Fortnow, Karloff, e Nisan [LFKN92].

2. coNP ⊂ IP 33

Um problema completo para a classe coNP é o de decidir se o número cromático χ(G) de um dado grafo G é ≥ 4, isto é, se G não admite uma coloração de seus vértices com no máximo 3 cores de forma que vértices adjacentes recebam cores distintas (para o conceito de completude veja Seção 2 do Capítulo V). Note que claramente este problema pertence à classe coNP, já que se G admite uma tal coloração, então exibindo uma destas colorações certificamos que χ(G) ≤ 3.

Seja dado um grafo G. Exibimos abaixo um jogo Artur–Merlin em que Merlin sempre vence se χ(G) ≥ 4, e o Rei Artur tem alta chance de vencer caso χ(G) ≤ 3, independentemente dos lances de Merlin. Começamos escolhendo um inteiro positivo N bastante grande em relação ao tamanho de G, e escolhemos um polinômio p(X) de grau 5 de coeficientes racionais tal que p(0) = 0 e p(t) = 1 se t ∈ {±1, ±2}. Suponha que o conjunto de vértices de G é {1, …, n}, e ponha

q(X_{1}, …, X_{n}) = ∏ p(X_{i} − X_{j}),

onde o produto se estende sobre todos pares i < j com ij uma aresta de G. Note que o polinômio q(X_{1}, …, X_{n}) tem grau total d ≤ 5|E(G)|. No que segue, usamos as cores 0, 1, e 2 para colorir os vértices de G. Ponha H = {0, 1, 2}. Então x ∈ H^{n} corresponde naturalmente a uma coloração dos vértices de G, e

q(x) = \begin{cases}1 & se x é uma coloração própria de G \\ 0 & caso contrário. \end{cases}  (1)

Desta forma, o número de colorações próprias de G é

q_{0} = ∑_{x∈H^{n}} q(x),

e é o objetivo de Merlin convencer o Rei Artur de que o valor q_{0} desta soma é nulo. Claramente, a definição explícita de q_{0} é uma soma sobre um conjunto de tamanho exponencial (‘experimente todas as possibilidades’), e assim não podemos esperar que o Rei Artur possa ingenuamente computar q_{0}, já que ele é polinomialmente limitado.

Para cada 1 ≤ i ≤ n, consideremos o polinômio racional

q_{i}(X_{1}, …, X_{i}) = ∑_{x_{i+1}∈H} ⋯ ∑_{x_{n}∈H} q(X_{1}, …, X_{i}, x_{i+1}, …, x_{n}) (2)

de i indeterminadas. Note que, trivialmente, temos

q_{i−1}(X_{1}, …, X_{i−1}) = ∑_{x_{i}∈H} q_{i}(X_{1}, …, X_{i−1}, x_{i})  (3)

para todo 1 ≤ i ≤ n. O jogo de Artur–Merlin é dado na Figura III.4.

Merlin declara inicialmente que q_{0} = q̂_{0} = 0.

Para cada i = 1, …, n, alternam-se os seguintes lances.

(1) Merlin fornece um polinômio racional q̂_{i}(X_{i}) de grau ≤ d ao Rei Artur, e declara que q̂_{i}(X_{i}) = q_{i}(ρ_{1}, …, ρ_{i−1}, X_{i});

(2) O Rei Artur verifica se q̂_{i−1}(ρ_{i−1}) ≠ ∑_{x_{i}∈H} q̂_{i}(x_{i}), e rejeita se este for o caso e o jogo termina. Caso contrário, o Rei escolhe uniformente ao acaso um inteiro ρ_{i} satisfazendo 1 ≤ ρ_{i} ≤ N, e fornece este valor a Merlin.

Finalmente, se q̂_{n}(ρ_{n}) = q(ρ_{1}, …, ρ_{n}), o Rei Artur aceita, e caso contrário o Rei rejeita.

Figura III.4. Protocolo lfkn

Assuma que q_{0} = 0 e descrevamos a estratégia de vitória para Merlin. Simplesmente, basta que os lances de Merlin no passo (1) do jogo sejam, de fato, q̂_{i}(X_{i}) = q_{i}(ρ_{1}, …, ρ_{i−1}, X_{i}) para todo 1 ≤ i ≤ N. Note que, então, a identidade (3) garante que o Rei Artur nunca rejeitará, e assim ele terá convencido o Rei de que q_{0} = 0 e, assim, de que χ(G) ≥ 4, como queríamos.

Suponha agora que Merlin está tentando certificar uma afirmativa falsa; isto é, admitamos que q_{0} ≠ 0. O nosso objetivo é obter uma estimativa superior para a probabilidade de que o Rei Artur acabe aceitando que q_{0} = 0 ou, equivalentemente, que χ(G) ≥ 4. Assuma, portanto, que o Rei acabou devolvendo aceita.

Suponha que q̂_{1}(X_{1}) passou o teste de consistência no passo (2) do jogo, isto é, suponha que q̂_{1}(0) + q̂_{1}(1) + q̂_{1}(2) = 0. Como estamos assumindo que q_{1}(0) + q_{1}(1) + q_{1}(2) = q_{0} ≠ 0, temos que os polinômios q̂_{1}(X_{1}) e q_{1}(X_{1}) diferem. Agora notemos que, como Merlin declarou que q̂_{1}(X_{1}) = q_{1}(X_{1}), ele declarou implicitamente que q_{1}(ρ_{1}) = q̂_{1}(ρ_{1}). Como ambos q̂_{1}(X_{1}) e q_{1}(X_{1}) são de grau no máximo d, sabemos que eles coincidem para no máximo d valores de X_{1}. Assim, a probabilidade de que seja correto o valor q̂_{1}(ρ_{1}) declarado por Merlin para q_{1}(ρ_{1}) é de no máximo d/N. Suponha que q̂_{1}(ρ_{1}) ≠ q_{1}(ρ_{1}). Consideraremos o caso em que há acidentalmente igualdade aqui como ‘azar’, e contabilizaremos a probabilidade correspondente na estimativa superior para a probabilidade de o Rei Artur ser ‘ludibriado’.

Observemos agora que a situação é a seguinte. Temos um polinômio racional q(ρ_{1}, X_{2}, …, X_{n}) com n−1 indeterminadas e Merlin declarou um valor errôneo para a soma

q_{1}(ρ_{1}) = ∑_{x_{2}∈H} ⋯ ∑_{x_{n}∈H} q(ρ_{1}, x_{2}, …, x_{n}),  (4)

a saber, q̂_{1}(ρ_{1}) ≠ q_{1}(ρ_{1}). Assim, estamos numa situação análoga àquela da qual partimos: no começo do jogo, Merlin havia declarado o valor errôneo 0 para a soma q_{0} = ∑_{x∈H^{n}} q(x). Entretanto, temos agora uma indeterminada a menos, e a soma é sobre o ‘hipercubo’ H^{n−1} de dimensão um menor.

Prosseguimos agora por indução, sempre assumindo que os valores declarados q̂_{i}(ρ_{i}) (1 ≤ i ≤ n) para as somas intermediárias

∑_{x_{i+1}∈H} ⋯ ∑_{x_{n}∈H} q(ρ_{1}, …, ρ_{i}, x_{i+1}, …, x_{n})

são incorretos. Analisemos o que acontece ao fim das n rodadas do jogo. Temos, neste ponto, os inteiros ρ_{1}, …, ρ_{n} e o polinômio q̂_{n}(X_{n}). Este polinômio é, de acordo com Merlin, o polinômio

q_{n}(ρ_{1}, …, ρ_{n−1}, X_{n}).  (5)

No último teste de consistência do Rei Artur no protocolo, ele verifica se

q̂_{n}(ρ_{n}) = q_{n}(ρ_{1}, …, ρ_{n}).  (6)

Como estamos admitindo que o Rei Artur aceitou a afirmativa de Merlin, a igualdade (6) verificou-se, o que ocorre com probabilidade no máximo d/N, já que q̂_{n}(X_{n}) não é o polinômio dado em (5).

Concluímos assim que a probabilidade de Merlin ludibriar o Rei Artur é de no máximo

∑_{0≤i≤n} (1 − \frac{d}{N} )^{i} \frac{d}{N} ≤ \frac{d(n + 1)}{N}.  (7)

Basta agora tomar N suficientemente grande para que d(n + 1)/N ≤ 1/4. Por exemplo, podemos tomar N = 20n^{3}, onde, recordamos, n é o número de vértices em G.

Assim certificamos a afirmativa χ(G) ≥ 4 através de uma prova interativa. Como mencionado acima, esta afirmativa é completa para a classe coNP, e portanto temos o seguinte resultado.

Teorema 12. coNP ⊂ IP.

Note que o resultado acima mostra que o problema de se certificar a não existência de um circuito hamiltoniano em um dado grafo pode ser resolvido através de um sistema de provas interativo, já que este problema pertence à classe coNP. Lembre que este foi um dos exemplos discutidos no Capítulo I (o ‘problema do banquete pacífico’).

Em realidade, o Protocolo lfkn pode ser usado para certificar o número de colorações próprias que um dado grafo G tem com k cores, onde k é qualquer inteiro fixo. Isto implica algo muito mais forte que o Teorema 12, embora este resultado seja mais ‘técnico’.

Suponha que uma máquina de Turing M tenha acesso a um oráculo que é capaz de responder perguntas do tipo ‘quanto é f(x)?’, onde f é uma função em #P (cf. Seção 3 do Capítulo II). O custo de cada consulta ao oráculo é aqui, por definição, unitário. A classe de linguagens que são reconhecidas em tempo polinomial por tais máquinas de Turing M é conhecida como a classe P^{#P}. O Protocolo lfkn fornece o seguinte resultado de Lund, Fortnow, Karloff, e Nisan [LFKN92].

Teorema 13. P^{#P} ⊂ IP.

Por um resultado de Toda [Tod89], a hierarquia polinomial (veja, por exemplo, Garey e Johnson [GJ76]) está contida em P^{#P}. Assim temos do resultado acima o seguinte corolário imediato.

Corolário 14. Toda linguagem na hierarquia polinomial admite um sistema interativo de prova.

Veremos na seção seguinte o resultado definitivo sobre o poder das provas interativas.

3. IP = PSPACE

A intenção ao se definir a classe AM foi a de se definir classes de linguagens um pouco maiores que NP. Nas palavras de Babai e Moran [BM88], “a hierarchy of complexity classes ‘just above NP’.” O resultado que descrevemos a seguir, que IP = PSPACE, foi uma surpresa para todos os pesquisadores da área. O poder de uma fonte de bits aleatórios num sistema de provas tinha sido subestimado.

Uma possível justificativa para tal fato é a seguinte. Existem classes de complexidade definidas de forma similar à classe P, com a diferença que agora os algoritmos têm acesso a uma fonte de bits aleatórios e se requer que a resposta seja apenas probabilisticamente correta. Esses algoritmos são chamados de algoritmos do tipo Monte Carlo. Classes de linguagens reconhecíveis por tais algoritmos foram definidas nos anos 70. Desde então, todos os esforços empreendidos na direção de se provar que essas classes contenham propriamente a classe P ou se igualem a classe NP foram em vão. Com isso, a comunidade passou a duvidar do poder computacional de elementos aleatórios em procedimentos algorítmicos.

Antes da prova que IP = PSPACE, precisamos fazer umas observações sobre a classe PSPACE. Podemos definir o similar da redução de Karp (Definição 46) para a classe PSPACE. Com essa nova redução podemos definir problemas completos para PSPACE, e provar o seguinte teorema.

Teorema 15. O Problema QBF é PSPACE-completo.

(Para a definição do Problema QBF veja Apêndice A.)

Para mostrar que IP = PSPACE comentaremos inicialmente que IP ⊆ PSPACE. A seguir, mostraremos que QBF está em IP. Como o Problema QBF é completo para PSPACE, isso implica que PSPACE ⊆ IP, encerrando a prova.

Teorema 16. IP = PSPACE.

Prova. Não é muito difícil ver que IP ⊆ PSPACE. Para uma máquina de Turing M′ reconhecer uma linguagem L ∈ IP usando espaço polinomial, basta que M′ simule, para cada possível conteúdo y da fita F_{P} e cada conteúdo τ da fita de bits aleatórios, a computação de V. A máquina M′ pára com resposta sim se e somente se para algum dos y e para qualquer τ, o verificador V pára com resposta sim. Caso contrário, M′ pára com resposta não.

Portanto, a parte difícil da prova é mostrar que PSPACE ⊆ IP. Para tanto, vamos mostrar que um problema completo para PSPACE, o problema QBF, está em IP.

A entrada do QBF é uma fórmula booleana quantificada

(Q_{1}x_{1})(Q_{2}x_{2}) … (Q_{k}x_{k})B(x_{1}, x_{2}, …, x_{k}),

onde Q_{i} é ou ∀ ou ∃ e B é uma fórmula booleana (sem quantificadores).

Para cada fórmula booleana B(x_{1}, x_{2}, …, x_{k}) podemos fazer corresponder um polinômio b(x_{1}, x_{2}, …, x_{k}), conhecido como a aritmetização da fórmula B, onde α ∧ β é substituído por αβ, ¬α por 1 − α e α ∨ β por α ⋆ β = α + β − αβ = 1 − (1 − α)(1 − β). Observe que os valores de B e b coincidem para argumentos booleanos, isto é, interpretando 1 como verdadeiro e 0 como falso.

Seja P (x, x_{1}, x_{2}, …, x_{k}) um polinômio. Definimos os seguintes polinômios a partir de P:

(A_{x}P)(x_{1}, x_{2}, …, x_{k}) = P (0, x_{1}, x_{2}, …, x_{k})P (1, x_{1}, x_{2}, …, x_{k}),
(E_{x}P)(x_{1}, x_{2}, …, x_{k}) = P (0, x_{1}, x_{2}, …, x_{k}) ⋆ P (1, x_{1}, x_{2}, …, x_{k}),
(R_{x}P)(x, x_{1}, x_{2}, …, x_{k}) = P mod (x^{2} − x)

(isto é, todas as ocorrências de x^{n} com n > 1 são substituídas por x).

Nos polinômios A_{x}P e E_{x}P a variável x está ausente, enquanto R_{x}P tem as mesmas variáveis de P. Note que P e R_{x}P coincidem em argumentos booleanos.

Seja S(x_{1}, x_{2}, …, x_{k}) um polinômio sobre um corpo finito C de cardinalidade |C|. Assuma que exista um sistema de provas interativo α em IP permitindo que Merlin convença Artur que S(u_{1}, u_{2}, …, u_{k}) = v com probabilidade 1 para qualquer entrada u_{1}, u_{2}, …, u_{k}, v ∈ C quando isso é verdadeiro, e com probabilidade menor que ε quando isso é falso. Seja U o polinômio obtido de S por uma das operações A_{x}, E_{x} ou R_{x}. Seja d o grau de x em S e suponha este valor conhecido por Artur. Vamos construir um sistema de provas interativo β permitindo a Merlin convencer Artur de que U(c_{1}, c_{2}, …, c_{t}) = e com probabilidade 1 para quaisquer c_{1}, c_{2}, …, c_{t}, e quando isso é verdadeiro e com probabilidade menor que ε + d/|C| quando isso é falso.

Descrevemos agora a construção do sistema de provas interativo β.

Caso A. U(y_{1}, …, y_{t}) = A_{x}S(x, y_{1}, …, y_{t}). Merlin quer convencer Artur de que U(c_{1}, c_{2}, …, c_{t}) = e. O protocolo está descrito na Figura III.5.

(1) Merlin envia a Artur os coeficientes do polinômio s(x) = S(x, c_{1}, …, c_{t}).

(2) Se o grau de s excede d ou s(0)s(1) ≠ e, Artur rejeita.

(3) Caso contrário, Artur envia a Merlin um elemento aleatório de r ∈ C.

(4) Usando o sistema de provas α, Merlin tenta convencer Artur de que S(r, c_{1}, …, c_{t}) = s(r).

Figura III.5. Protocolo para o Caso A

Caso E. U(y_{1}, …, y_{t}) = E_{x}S(x, y_{1}, …, y_{t}). Troca-se, no caso anterior, s(0)s(1) por s(0) ⋆ s(1).

Caso R. U(x, y_{1}, …, y_{t}) = R_{x}S(x, y_{1}, …, y_{t}). Merlin quer convencer Artur de que U(f, c_{1}, c_{2}, …, c_{t}) = e. O protocolo está descrito na Figura III.6.

Merlin pode enganar Artur ou durante α (com probabilidade menor que ε) ou se polinômios diferentes s(x) e S(x, c_{1}, …, c_{t}) coincidem no ponto aleatório r (probabilidade menor que d/|C|).

Seja F = (Q_{1}x_{1})(Q_{2}x_{2}) … (Q_{k}x_{k})B(x_{1}, x_{2}, …, x_{n}) uma fórmula booleana quantificada. Considere a aritmetização b(x_{1}, x_{2}, …, x_{n}) de B e aplique, seqüencialmente, operações conforme descritas na Figura III.7. Nessa figura q_{i}x = A_{x} ou E_{x} conforme Q_{i} = ∀ ou ∃. Após essas operações obtemos uma constante igual a 0 ou 1, dependendo da validade da fórmula F. Se a constante é 1, Merlin pode convencer Artur desse fato. Para tanto, o trabalho inicial de Merlin é aplicar no polinômio b as operações descritas acima que resultaram na constante 1. Após essa fase, Merlin precisa convencer Artur de que cada (1) Merlin envia a Artur os coeficientes do polinômio s(x) =

S(x, c_{1}, …, c_{t}).

(2) Se o grau de s excede d ou s(0) + (s(1) − s(0))f ≠ e, Artur rejeita.^{†}

(3) Caso contrário, Artur envia a Merlin um elemento aleatório de r ∈ C.

(4) Usando os sistema de provas α, Merlin tenta convencer Artur de que S(r, c_{1}, …, c_{t}) = s(r).

†Observe que s(0) + (s(1) − s(0))f é o valor de s(x) mod (x^{2} − x) em f.

Figura III.6. Protocolo para o Caso R

operação foi feita corretamente. Isso é feito seguindo a seqüência de operações de ‘baixo para cima.’ Em cada passo Merlin usa o sistema β para convencer Artur de que a operação foi aplicada corretamente. Finalmente, a igualdade b(u_{1}, u_{2}, …, u_{n}) = v precisa ser verificada para algum u_{1}, u_{2}, …, u_{n}, v. Artur pode fazer isso sozinho pois a fórmula B é conhecida. A probabilidade de erro não excede

\frac{(número de operações A, E, R)×(grau máximo)}{|C|}.

Se o comprimento da fórmula F é l, então o número de operações é O(l^{2}). O grau máximo de b não excede l e as operações R reduzem o grau a 1, sendo que posteriormente os graus são no máximo 2. Se C tem mais do que l^{4} elementos, a probabilidade de erro tende a 0 quando l → ∞. Podemos usar C = ℤ/pℤ, onde p é um primo de comprimento logarítmico em l. O primo p pode ser escolhido por Artur, pois o teste de primalidade é trivial para números desse tamanho. □

4. Notas Bibliográficas

A classe IP foi definida por Goldwasser, Micali, e Rackoff [GMR85], e a classe AM por Babai [Bab85]. Os trabalhos independentes apresentando essas classes aparecem simultaneamente numa mesma conferência. Um ano depois, Goldwasser e Sipser [GS86] provam o Teorema 10 mostrando a equivalência dessas classes. O Teorema 11 é

\begin{matrix}R_{x_{1}}, R_{x_{2}}, …, R_{x_{n}}, \\ q_{n}x_{n}, \\ R_{x_{1}}, R_{x_{2}}, …, R_{x_{n−1}}, \\ q_{n−1}x_{n−1}, \\ ⋯ \\ R_{x_{1}}, R_{x_{2}}, \\ q_{2}x_{2}, \\ R_{x_{1}}, \\ q_{1}x_{1}, \end{matrix}

Figura III.7. Operações sobre b

de Babai e Moran [BM88]. Goldreich discute em [Gol94] vários sistemas de provas, salientando a importância dos elementos aleatórios em todos eles.

Os resultados da Seção 2 são todos devidos a Lund, Fortnow, Karloff, e Nisan. Em [LFKN92], estes autores dão uma prova de que o valor do permanente de uma matriz pode ser certificado através de uma prova interativa. Como provado por Valiant [Val79], esta função é completa para a classe #P, e assim segue o Teorema 13, o resultado central da Seção 2. A prova alternativa aqui apresentada é devida a Babai [Bab94].

O Teorema 15 é de Stockmeyer [Sto76]. O resultado IP = PSPACE é devido a Shamir [Sha92]. A demonstração original deste teorema segue de perto Lund, Fortnow, Karloff, e Nisan [LFKN92]. Veja Babai [Bab90] para uma discussão muito interessante sobre a história deste resultado. A demonstração simplificada dada acima é devida a Shen [She92].

42 III. PROVAS INTERATIVAS

CAPÍTULO IV PROVAS VERIFICÁVEIS PROBABILISTICAMENTE

Neste capítulo discutiremos a demonstração do resultado central de Arora, Lund, Motwani, Sudan, e Szegedy [ALM^{+}92b]. Lembremos rapidamente o que diz este resultado. Seja L um linguagem NP, ou seja, uma linguagem cujos elementos x ∈ L admitem certificados de pertinência y_{x} simples e curtos. Intuitivamente, isto significa que para que ‘provemos’ que x ∈ L, basta apresentarmos este certificado y_{x} como uma demonstração deste fato. Sendo simples e curta, esta prova pode ser eficientemente verificada em tempo polinomial.

Informalmente, o resultado de Arora et al. diz que se L ∈ NP, então todo elemento x ∈ L também admite um certificado de pertinência Π_{x} transparente. Para que fiquemos convencidos de que x ∈ L, basta lermos um número O(1) de caracteres de Π_{x}. Os caracteres a serem lidos são escolhidos aleatoriamente, mas o número de bits aleatórios usados para se sortear estes caracteres é O(log n), onde como de usual n = |x|.

1. O Sistema de Provas PCP

Aqui descrevemos precisamente o sistema de provas em que se baseiam as demonstrações transparentes. Neste capítulo, sempre teremos Σ = {0, 1} e, sem perda de generalidade, consideramos linguagens L ⊂ Σ^{∗} apenas.

No sistema de provas PCP (Probabilistically Checkable Proofs), o verificador V é uma máquina de Turing determinística de complexidade de tempo polinomial que recebe como entrada uma palavra x ∈ Σ^{∗} e que tem acesso a uma seqüência de bits aleatórios τ ∈ Σ^{∗}. Este verificador também tem acesso a uma palavra Π = π_{1}π_{2} … π_{|Π|} ∈ Σ^{∗} através de um oráculo. Uma vez dadas a entrada x e a seqüência de bits aleatórios τ, o verificador V ‘sabe’ quais caracteres π_{i} de Π ele vai querer acessar durante a sua computação; em outras palavras, uma vez dadas x e τ, o verificador V pode pedir ao oráculo que lhe dê, de uma vez, todos os caracteres π_{i_{1}}, …, π_{i_{ℓ}} de que V necessitará, não sendo o valor destes caracteres levado em conta na decisão de quais caracteres serão lidos. Assim, a seqüência i_{1}, …, i_{ℓ} é determinada apenas com base em x e τ, e portanto dizemos algumas vezes que o verificador V é não-adaptativo. No fim de sua computação, V deve dizer se aceita ou não a entrada x; a saída, denotada por V (x, τ, Π), será aceita ou rejeita.

Sejam r(n) e q(n) duas funções reais definidas sobre os inteiros não negativos n. Um verificador V é dito ser (r(n), q(n))-restrito se existem duas funções inteiras r̂(n) = O(r(n)) e q̂(n) = O(q(n)) tais que V, com qualquer entrada x de comprimento |x| = n e qualquer seqüência de bits aleatórios τ, faz uso em sua computação de não mais do que os primeiros r̂(n) bits de τ, e pede ao oráculo não mais que q̂(n) caracteres π_{i} de Π. No que segue, escrevemos ℙ_{τ} para denotar probabilidade com respeito à seqüência de bits aleatórios τ. Formalmente, embora os nossos verificadores sempre usem apenas um segmento inicial finito de τ, podemos assumir que τ tem comprimento infinito.

Definição 17. A linguagem L ⊂ Σ^{∗} está em PCP(r(n), q(n)) se e só se existe um verificador (r(n), q(n))-restrito V para o qual valem as seguintes duas afirmativas.

(i) Para todo x ∈ L, existe uma prova Π = Π_{x} ∈ Σ^{∗} tal que

ℙ_{τ} {V (x, τ, Π) = aceita} = 1.  (8)

(ii) Para todo x ∉ L e para todo Π ∈ Σ^{∗}, temos

ℙ_{τ} {V (x, τ, Π) = aceita} < 1/4.  (9)

Note que na definição acima, o valor da constante 1/4 não tem um papel muito importante. Substituindo-se aquele valor por qualquer constante θ < 1, obteríamos para PCP(r(n), q(n)) a mesma classe de linguagens. O motivo é simples: um verificador para o qual temos

ℙ_{τ}{V (x, τ, Π_{x}) = aceita} < θ  (10)

pode ser transformado em um que satisfaz (9) acima por iteração.

Por conveniência, se Φ_{1} e Φ_{2} são duas classes de funções reais definidas sobre os inteiros não negativos, poremos

PCP(Φ_{1}, Φ_{2}) = ⋃_{f∈Φ_{1},g∈Φ_{2}} PCP(f, g).

Como de usual, poly(n) denota o conjunto de todos os polinômios p(n).

Quando sistemas de provas PCP estão sob consideração, usamos o termo genérico provas transparentes para os certificados Π da Definição 17. Caso mais precisão seja necessária, quando uma linguagem em PCP(r(n), q(n)) esteja sob consideração, referiremo-nos a Π_{x} como em (i) acima como uma prova, demonstração, ou certificado (r(n), q(n))-transparente.

O resultado central deste capítulo, devido a Arora, Lund, Motwani, Sudan, e Szegedy [ALM^{+}92b], pode ser formulado como segue.

Teorema 18. PCP(log n, 1) = NP.

Já existem hoje versões mais finas do que o resultado acima. Mencionamos apenas duas delas. Para enunciar o primeiro refinamento, introduzimos a seguinte notação. Dizemos que uma linguagem L ⊂ Σ^{∗} pertence a classe PCP′(r(n), q(n)) se existe um verificador associado V tal que todo x ∈ L de comprimento |x| = n admite uma prova transparente Π reconhecida por V usando O(r(n)) bits aleatórios e acessando em média não mais que q(n) caracteres de Π. Lembre que os caracteres de Π a serem acessados no processo de verificação são definidos de acordo com x, a entrada, e τ, a seqüência de bits aleatórios. Assim, o número de caracteres a serem lidos é uma variável aleatória; a média acima refere-se às seqüências aleatórias τ. O seguinte refinamento do Teorema 18 segue de resultados provados por Bellare, Golwasser, Lund, e Russel [BGLR93, BGLR94].

Teorema 19. PCP′(log n, 100) = NP.

Não é difícil de deduzir do resultado acima que não só o número esperado de caracteres da prova a serem lidos pode ser limitado por uma constante universal, mas também podemos garantir que nunca leremos mais do que uma certa quantidade constante de caracteres da prova.

O segundo refinamento do Teorema 18 é o seguinte resultado provado por Polishchuk e Spielman [PS94], em que o comprimento dos certificados transparentes é investigado.

Teorema 20. Seja ε > 0 uma constante arbitrária e suponha que L ∈ NP. Suponha que x ∈ L e y é um certificado polinomial da pertinência de x à linguagem L. Ponha n = |x| + |y|. Então existe uma prova (log n, 1)-transparente da pertinência de x à L de comprimento O(n^{1+ε}).

A demonstração de Arora et al. do Teorema 18 fornece provas transparentes de comprimento superquadrático, e o resultado acima nos diz que provas transparentes de comprimento quase-linear existem.

Fechamos esta seção com o seguinte comentário. Podemos pensar no verificador V como sendo uma máquina de Turing que, dados x e τ, constrói em tempo polinomial um circuito booleano C_{τ} = C_{τ,x} que tem variáveis de entrada y = y_{1} … y_{ℓ}. Quando o oráculo fornece os caracters q_{i_{1}} … q_{i_{ℓ}} da prova Π a V, o resultado V (x, τ, Π) da computação de V é o mesmo que o resultado que obtemos quando fornecemos a entrada y = q_{i_{1}} … q_{i_{ℓ}} a C_{τ} = C_{τ,x}. Esta formalização é usada por Arora et al. em [ALM^{+}92b]. Aqui seguimos Arora et al. [ALM^{+}92a] e Hougardy, Prömel, e Steger [HPS94], que adotam uma formalização mais combinatória.

2. A Estrutura da Demonstração

Descrevemos aqui a estrutura da demonstração do Teorema 18. Comecemos observando que a inclusão PCP(log n, 1) ⊂ NP é bastante simples. De fato, o resultado genérico abaixo vale. Lembre que denotamos por NTIME(f(n)) a classe de linguagens reconhecidas por sistemas de prova conforme a Definição 4 da Seção 2.1 do Capítulo II. Como de usual, se Φ é uma classe de funções, pomos

NTIME(Φ) = ⋃_{f∈Φ} NTIME(f).

Em particular, NTIME(poly(n)) = NP.

Lema 21. PCP(r(n), q(n)) ⊂ NTIME (poly(n2^{r(n)})).

Prova. As seguintes observações simples são suficientes para provar o nosso lema. Suponha que temos uma linguagem L ⊂ Σ^{∗} que pertence à classe PCP(r(n), q(n)), e seja V um verificador (r(n), q(n))- restrito associado. Seja dado x ∈ L e suponha que Π é uma prova (r(n), q(n))-transparente da pertinência de x à L. Uma vez fixada a seqüência aleatória de bits τ, o comportamento de V é determinístico. Assim, basta provar que é possível simular o comportamento de V para todos os possíveis τ através de um sistema NTIME de provas em que o verificador leva tempo O (poly(n2^{r(n)})) no total. Note que há apenas 2^{O(r(n))} seqüências τ a serem consideradas. Cada uma delas define O(q(n)) posições da prova Π a serem examinadas. Assim, não mais que O(q(n)2^{O(r(n))}) entradas de Π serão examinadas no processo inteiro. Construa, a partir de Π, uma seqüência Π′ contendo todos os caracters de Π ‘relevantes’ para o processo de verificação executado por V. Simulando o comportamento de V sobre todos os possíveis τ, usando Π′ como a fita do provador no sistema NTIME de provas, podemos decidir se x pertence ou não a L. De fato, x pertence a L se e só se V aceita x para todo τ. Claramente, o verificador no sistema NTIME de provas leva não mais que tempo n^{O(1)}2^{O(r(n))} para executar a simulação descrita acima. □

Segue do Lema 21 que PCP(log n, 1) ⊂ NP. O ‘conteúdo’ do Teorema 18 é que a inclusão reversa vale. Seja L ∈ Σ^{∗} uma linguagem NP. Para demonstrarmos que L ∈ PCP(log n, 1), devemos (i) descrever como obter uma prova transparente Π_{x} para todo x ∈ L e (ii) descrever um verificador (log n, 1)-restrito V associado que reconhece estas demonstrações como tais, e que, se x ∉ L, não pode ser ludibriado com probabilidade ≥ 1/4 por ‘demonstrações incorretas’ de que x ∈ L.

Suponha que L ⊂ Σ^{∗} é uma linguagem em NP e que x ∈ L. Então sabemos que existe um certificado polinomial y_{x} ∈ Σ^{∗} para a pertinência de x em L. Para demonstrarmos que L ∈ PCP(r(n), q(n)) para r(n) e q(n) dados, codificaremos y_{x} através de uma função cuidadosamente construída E: Σ^{∗} → Σ^{∗} de forma a obter uma prova transparente Π_{x} = E(x) para a pertinência de x em L.

Basicamente, a demonstração de que NP ⊂ PCP(log n, 1) é composta de três passos.

(1) Exibe-se primeiro uma codificação E: Σ^{∗} → Σ^{∗} e um verificador (poly(n), 1)-restrito associado V que demonstram conjuntamente que

NP ⊂ PCP(poly(n), 1).

(2) Exibe-se então uma codificação E′: Σ^{∗} → Σ^{∗} e um verificador associado (log n, poly(log n))-restrito V′ que provam que

NP ⊂ PCP(log n, poly(log n)).

(3) Mostra-se finalmente que as codificações E e E′ e os verificadores V e V′ acima podem ser ‘compostos’ de forma a se obter uma codificação E′′ e um verificador (log n, 1)-restrito V′′, demonstrando-se assim que NP ⊂ PCP(log n, 1).

No resto deste capítulo, discutimos os três passos acima.

3. A Demonstração

3.1. Certificados transparentes I. Objetivamos provar aqui que NP ⊂ PCP(poly(n), 1). Seja L ⊂ Σ^{∗} uma linguagem em NP. Precisamos provar que todo x ∈ L admite um certificado (poly(n), 1)- transparente Π_{x} e precisamos contruir um verificador (poly(n), 1)- restrito associado V para reconhecer tais certificados.

Note que os certificados Π_{x} de que trataremos aqui têm uma característica comum com os certificados cuja existência está implícita no Teorema 18. De fato, os certificados Π_{x} não precisam ser lidos inteiros. Muito pelo contrário, para que o verificador fique satisfeito de que Π_{x} é um certificado válido da afirmativa ‘x ∈ L’, basta que ele leia um número O(1) de entradas de Π_{x}.

Por outro lado, cabe ressaltar que os verificadores desta subseção exigem acesso a um número polinomial de bits aleatórios, e não apenas logarítmico. Veremos que este fato é uma conseqüência do comprimento dos certificados Π_{x} que construiremos. De fato, os Π_{x} que construiremos abaixo terão tamanho exponencial no tamanho de x. Note que isto implica que, se quisermos acessar uma entrada de Π_{x} escolhida uniformemente ao acaso, precisamos fazer uso de uma quantidade polinomial de bits aleatórios.

Concluímos com uma observação que nos porá na direção certa para começarmos a demonstração da inclusão NP ⊂ PCP(poly(n), 1). Recordemos o resultado clássico que afirma que 3sat é um problema NP-completo (veja o Teorema 53 da Seção 2 do Capítulo V). Desta forma, para mostrarmos a inclusão acima, basta que provemos que toda instância satisfatível x de 3sat admite um certificado (poly(n), 1)- transparente e que construamos um verificador associado apropriado. O certificado que construiremos abaixo será (n^{3}, 1)-transparente.

3.1.1. A aritmetização. O primeiro passo para demonstrarmos que 3sat ∈ PCP(n^{3}, 1) é a aritmetização deste problema. Esta idéia apareceu na demonstração do resultado de que IP = PSPACE (Teorema 16 do Capítulo III). De fato, uma idéia básica lá foi a de tratar fórmulas booleanas como polinômios—a idéia aqui é a mesma. Seja φ uma instância de 3sat com m cláusulas e n variáveis. Assim φ é uma família de m cláusulas C_{i} (1 ≤ i ≤ m), onde cada cláusula C_{i} é uma família de três literais ℓ_{j}^{(i)} (j ∈ {1, 2, 3}). Cada literal é uma variável x_{k} ou a sua negação ¬x_{k} (1 ≤ k ≤ n). A interpretação de φ é que ela representa a fórmula booleana

(ℓ_{1}^{(1)} ∨ ℓ_{2}^{(1)} ∨ ℓ_{3}^{(1)}) ∧ ⋯ ∧ (ℓ_{1}^{(m)} ∨ ℓ_{2}^{(m)} ∨ ℓ_{3}^{(m)}).  (11)

O problema 3sat consiste em descobrir se φ admite uma atribuição de valores a: U = {x_{k}: 1 ≤ k ≤ n} → {V, F} tal que φ(a) = V. Um argumento simples mostra que podemos nos restringir aqui a instâncias 3sat com m = n. No que segue, sempre admitiremos isto.

A aritmetização C = C(φ) de φ que consideraremos aqui é a seguinte: C será um vetor (C_{1}(x), …, C_{n}(x)) de n polinômios C_{i}(x) (1 ≤ i ≤ n) sobre as variáveis x = (x_{1}, …, x_{n}). Aqui usamos a mesma notação para as variáveis booleanas de φ e para as indeterminadas de C. O polinômio C_{i}(x) é a aritmetização da negação ¬C_{i} de C_{i} no sentido encontrado na demonstração do Teorema III.16.

Por exemplo, se

φ = (x_{1} ∨ ¬x_{2} ∨ ¬x_{3}) ∧ (¬x_{2} ∨ x_{3} ∨ x_{4}) ∧ (¬x_{1} ∨ ¬x_{2} ∨ x_{4}), (12)

então

C(φ) = ((1 − x_{1})x_{2}x_{3}, x_{2}(1 − x_{3})(1 − x_{4}), x_{1}x_{2}(1 − x_{4})). (13)

Note que há, no total, quatro possibilidades para cada um dos polinômios C_{i}(x), a menos das indeterminadas envolvidas.

No que segue, sempre trabalhamos no corpo 𝔽_{2} = GF(2). Uma observação imediata mas importante é que a: U → {V, F} é uma atribuição que satisfaz φ se e só se o vetor em 𝔽_{2}^{n} naturalmente associado a a é tal que C(a) = 0 ∈ 𝔽_{2}^{n}. Desta forma, podemos convencer alguém de que φ é satisfatível convencendo-o de que C(a) = 0 para algum vetor a ∈ 𝔽_{2}^{n}. A idéia agora é que nós conhecemos a ∈ 𝔽_{2}^{n} tal que C(a) = 0, e que queremos escrever uma prova transparente deste fato.

3.1.2. Discussão informal. O contexto em que trabalhamos aqui é o seguinte. Temos uma instância φ de 3sat com n variáveis x_{i} (1 ≤ i ≤ n) e n cláusulas C_{i} (1 ≤ i ≤ n). A aritmetização de φ é C = C(φ) = (C_{i}(x))_{1≤i≤n}, onde cada C_{i}(x) é um polinômio nas indeterminadas x = (x_{i})_{1≤i≤n}. Mais precisamente, cada C_{i}(x) é um polinômio com no máximo três indeterminadas e é, a menos das indeterminadas, um dos seguintes polinômios: P_{1} = xyz, P_{2} = xy(1 − z), P_{3} = x(1 − y)(1 − z), P_{4} = (1 − x)(1 − y)(1 − z). Finalmente, supomos que temos uma atribuição de valores a para as variáveis de φ que satisfaz φ e, assim, que temos a = (a_{i})_{1≤i≤n} ∈ 𝔽_{2}^{n} tal que C(a) = 0.

Consideremos ⟨C(a), r⟩ para um vetor r = (r_{i})_{1≤i≤n} ∈ 𝔽_{2}^{n}, onde

⟨u, v⟩ = ⟨(u_{i})_{1≤i≤n}, (v_{i})_{1≤i≤n}⟩ = ∑_{1≤i≤n} u_{i}v_{i}

denota o produto escalar canônico em 𝔽_{2}^{n}. Note que

⟨C(a), r⟩ = c + ∑_{i∈S_{1}(r)} a_{i} + ∑_{(i,j)∈S_{2}(r)} a_{i}a_{j} + ∑_{(i,j,k)∈S_{3}(r)} a_{i}a_{j}a_{k}, (14)

onde c = c_{r} ∈ 𝔽_{2}, S_{1}(r) ⊂ [n], S_{2}(r) ⊂ [n]^{2}, e S_{3}(r) ⊂ [n]^{3} são univocamente determinados por r apenas e, em particular, independem de a. Acima, como de costume, [n] = {1, …, n}. Desta forma, se temos acesso aos valores de

∑_{i∈S_{1}} a_{i},  ∑_{(i,j)∈S_{2}} a_{i}a_{j},  ∑_{(i,j,k)∈S_{3}} a_{i}a_{j}a_{k}  (15)

para todos os possíveis conjuntos S_{1} ⊂ [n], S_{2} ⊂ [n]^{2}, e S_{3} ⊂ [n]^{3}, o valor de ⟨C(a), r⟩ pode ser facilmente obtido para qualquer r ∈ 𝔽_{2}^{n}. O certificado transparente Π = Π_{φ} de que φ é satisfatível será composto dos valores das somas em (15) para todos os possíveis S_{1}, S_{2}, e S_{3}.

Como deve agir o verificador para interpretar este certificado? A idéia é simples: para que ele fique satisfeito com o fato de que C(a) = 0, basta-lhe calcular ⟨C(a), r⟩ para vários r ∈ 𝔽_{2}^{n} escolhidos ao acaso. Note que, devido a (14), cada um destes cálculos pode ser feito consultando-se o certificado Π_{φ} apenas três vezes. Ademais, cada um destes produtos escalares é trivialmente nulo caso C(a) = 0. O verificador deve aceitar φ se e só se todos estes produtos forem de fato nulos.

Consideremos agora o caso em que φ não é satisfatível, e que o verificador recebeu algum Π ∈ Σ^{∗} como um certificado da satisfatibilidade de φ. O primeiro passo do verificador é sempre fazer uma análise de coerência de Π. Isto é, ele deve se satisfazer de que Π tem o ‘formato’ correto. Mais especificamente, ele deve se certificar de que Π de fato apresenta as somas em (15) para algum a ∈ 𝔽_{2}^{n}. Uma vez convencido deste fato, o verificador irá então calcular ⟨C(a), r⟩ para vários r ∈ 𝔽_{2}^{n} escolhidos ao acaso, usando as somas em (15).

A observação simples mas crucial neste ponto é que, como C(a) não é nulo, o produto ⟨C(a), r⟩ tem probabilidade 1/2 de ser não nulo quando escolhemos r ∈ 𝔽_{2}^{n} ao acaso. Assim, se o verificador calcula ⟨C(a), r⟩ para três vetores r ∈ 𝔽_{2}^{n} escolhidos independentemente, a probabilidade de todos os produtos escalares serem nulos é 1/8. Em outras palavras, o verificador será ludibriado com probabilidade no máximo 1/8. Devemos agora formalizar a discussão acima.

3.1.3. Codificações lineares. Como na discussão informal acima, suponha que C(a) = 0. Comecemos observando que as somas em (15) podem ser codificadas como três aplicações lineares. De fato, ponha b_{ij} = a_{i}a_{j} e c_{ijk} = a_{i}a_{j}a_{k} (1 ≤ i, j, k ≤ n), e

b = a ∘ a = (b_{ij})_{1≤i,j≤n} ∈ 𝔽_{2}^{n^{2}}, c = a ∘ a ∘ a = (c_{ijk})_{1≤i,j,k≤n} ∈ 𝔽_{2}^{n^{3}}, (16)

e considere as aplicações

A: 𝔽_{2}^{n} → 𝔽_{2},  B: 𝔽_{2}^{n^{2}} → 𝔽_{2},  C: 𝔽_{2}^{n^{3}} → 𝔽_{2},  (17)

dadas por

A(x) = ⟨a, x⟩,  B(y) = ⟨b, y⟩,  C(z) = ⟨c, z⟩  (18)

para todo x ∈ 𝔽_{2}^{n}, y ∈ 𝔽_{2}^{n^{2}}, e z ∈ 𝔽_{2}^{n^{3}}. O certificado transparente Π_{φ} de que φ é satisfatível será então o conjunto das três aplicações lineares homogêneas A, B e C, dadas como uma seqüência 0–1 de comprimento 2^{n} + 2^{n^{2}} + 2^{n^{3}}. Mais precisamente, pensamos em Π_{φ} como um elemento de Σ^{∗} daquele comprimento, com cada um de seus caracteres indexados por um elemento de 𝔽_{2}^{n} ∪ 𝔽_{2}^{n^{2}} ∪ 𝔽_{2}^{n^{3}}.

Devemos agora descrever um verificador (n^{3}, 1)-restrito V que reconhece tais certificados Π_{φ}.

3.1.4. O verificador. Suponha que temos uma instância φ de 3sat como na discussão informal acima. Temos ainda Π ∈ Σ^{∗} de comprimento 2^{n} + 2^{n^{2}} + 2^{n^{3}}, fornecida a nós como um certificado da satisfatibilidade de φ como descrito acima. O nosso objetivo é descrever um processo que verifica se Π é de fato um certificado ‘correto’.

O nosso procedimento é composto de três passos, que podem ser descritos, a grosso modo, como segue.

1. Verificamos primeiro se Π codifica três aplicações lineares A, B, e C como em (17). Caso descubramos que este não é o caso, rejeitamos φ e o procedimento termina.

2. Verificamos agora se os vetores a, b, e c associados às aplicações lineares A, B, e C satisfazem as relações de consistência (16). Caso descubramos que elas não são satisfeitas, o procedimento termina rejeitando φ.

3. Finalmente, convencidos de que Π codifica um vetor a ∈ 𝔽_{2}^{n} como esperado, verificamos probabilisticamente se C(a) = 0. A saber, verificamos se ⟨C(a), r⟩ = 0 para um número suficientemente grande de r ∈ 𝔽_{2}^{n} escolhidos independentemente ao acaso. Caso todos os produtos escalares calculados sejam nulos, aceitamos φ e, caso contrário, rejeitamos φ.

Tendo em mente a discussão informal acima, deve ser claro que o Passo 3 pode ser executado sem problemas por um verificador (n^{3}, 1)- restrito. Passamos agora a discutir os Passos 1 e 2.

3.1.5. O teste de linearidade. Descrevemos aqui um procedimento surpreendentemente simples para implementar o Passo 1 acima do nosso processo de verificação. Dado que Π tem comprimento 2^{n} + 2^{n^{2}} + 2^{n^{3}}, podemos assumir que Π representa três funções

Ã: 𝔽_{2}^{n} → 𝔽_{2},  B̃: 𝔽_{2}^{n^{2}} → 𝔽_{2},  C̃: 𝔽_{2}^{n^{3}} → 𝔽_{2}.  (19)

Note que, trivialmente, se devemos consultar apenas O(1) entradas de Π, não há como verificar se Ã, B̃, e C̃ são ‘exatamente’ lineares. O que fazemos é verificar se elas são próximas a funções lineares. No que segue, todas as nossas funções lineares serão homogêneas.

Sejam f e g duas funções definidas sobre um conjunto finito Ω, e seja 0 ≤ δ ≤ 1 um número real. Dizemos que f e g são δ-próximos se f(ω) = g(ω) para pelo menos (1 − δ)|Ω| elementos ω ∈ Ω. Equivalentemente, tomando-se a distribuição uniforme sobre Ω, temos que f e g são δ-próximos se

ℙ_{ω∈_{R}Ω}{f(ω) = g(ω)} ≥ 1 − δ,

onde escrevemos ℙ_{ω∈_{R}Ω} ou simplesmente ℙ_{ω} para denotar probabilidade sobre o espaço uniforme Ω. No que segue, escrevemos ω ∈_{R} Ω quando ω é escolhido uniformemente ao acaso em Ω.

O que é feito no Passo 1 do processo de verificação consiste em descobrir se Ã, B̃, e C̃ são δ-próximos a funções lineares A, B, e C, para algum δ > 0 cuidadosamente escolhido. Esta verificação pode ser feita com base no seguinte resultado.

Teorema 22. Seja 0 ≤ δ < 1/3 uma constante, e seja f̃: 𝔽_{2}^{n} → 𝔽_{2} uma função tal que

ℙ_{x,y}{f̃(x + y) ≠ f̃(x) + f̃(y)} ≤ δ/2,

onde x, y ∈ 𝔽_{2}^{n} são independentemente escolhidos uniformemente ao acaso. Então existe uma única função linear homogênea f: 𝔽_{2}^{n} → 𝔽_{2} que é δ-próxima à função f̃.

Prova. Defina a função f: 𝔽_{2}^{n} → 𝔽_{2} pondo

f(x) = \begin{cases}0 & se ℙ_{y}\{f̃(x + y) − f̃(y) = 0\} \\ & ≥ ℙ_{y}\{f̃(x + y) − f̃(y) = 1\} \\ 1 & caso contrário. \end{cases}

Provamos abaixo que esta funcão f é δ-próxima à f̃ e que ela é linear homogênea. Suponha inicialmente por absurdo que f e f̃ não são δpróximas. Então temos que ℙ_{x}{f(x) ≠ f̃(x)} > δ. Por outro lado, pela definição de f, temos que ℙ_{y}{f(x) = f̃(x + y) − f̃(y)} ≥ 1/2 para todo x ∈ 𝔽_{2}^{n}. Deduzimos que

ℙ_{x,y}{f̃(x + y) ≠ f̃(x) + f̃(y)} > δ/2,

o que contradiz a hipótese do nosso lema. Assim concluímos que f e f̃ são de fato δ-próximas. Provemos agora a linearidade de f.

Para todo a ∈ 𝔽_{2}^{n}, ponha

p_{a} = ℙ_{x}{f(a) = f̃(a + x) − f̃(x)}.

Observamos acima que, claramante, p_{a} ≥ 1/2. Afirmamos agora que p_{a} ≥ 1 − δ para todo a ∈ 𝔽_{2}^{n}. Para provar esta afirmativa, fixe a e observe que temos

ℙ_{x,y}{f̃(x + a) + f̃(y) ≠ f̃(x + a + y)} ≤ δ/2,

e

ℙ_{x,y}{f̃(x) + f̃(a + y) ≠ f̃(x + a + y)} ≤ δ/2,

e assim

ℙ_{x,y}{f̃(a + x) − f̃(x) ≠ f̃(a + y) − f̃(y)} ≤ δ.

Portanto, temos que

1 − δ ≤ ℙ_{x,y}{f̃(a + x) − f̃(x) = f̃(a + y) − f̃(y)}

= ∑_{z∈{0,1}} ℙ_{x}{f̃(a + x) − f̃(x) = z}^{2} = p_{a}^{2} + (1 − p_{a})^{2}.

Lembrando que p_{a} ≥ 1/2, temos que

1 − δ ≤ p_{a}^{2} + (1 − p_{a})^{2} ≤ p_{a}^{2} + p_{a}(1 − p_{a}) = p_{a},

como afirmamos acima. Usamos agora este fato para demonstrar que f é linear.

Fixe a, b ∈ 𝔽_{2}^{n}. Temos pela afirmativa acima que

p_{a} = ℙ_{x}{f(a) + f(b) + f̃(x) ≠ f̃(a + x) + f(b)} ≤ δ,
p_{b} = ℙ_{x}{f(b) + f̃(a + x) ≠ f̃(a + b + x)} ≤ δ,
p_{a+b} = ℙ_{x}{f̃(a + b + x) ≠ f(a + b) + f̃(x)} ≤ δ.

Segue que

ℙ_{x}{f(a) + f(b) + f̃(x) = f(a + b) + f̃(x)} ≥ 1 − 3δ > 0. (20)

Como o evento considerado no lado esquerdo de (20) é independente de x, temos que a probabilidade correspondente é 0 ou 1, e daí segue o resultado. □

Um teste de linearidade imediato do Teorema 22 é dado na Figura IV.8.

Escolha x, x′ ∈_{R} 𝔽_{2}^{n}, e verifique se Ã(x + x′) = Ã(x) + Ã(x′).

Escolha y, y′ ∈_{R} 𝔽_{2}^{n^{2}}, e verifique se B̃(y + y′) = B̃(y) + B̃(y′).

Escolha z, z′ ∈_{R} 𝔽_{2}^{n^{3}}, e verifique se C̃(z + z′) = C̃(z) + C̃(z′).

Figura IV.8. O Teste de Linearidade

Naturalmente, se uma das igualdades no Teste de Linearidade não for satisfeita, o verificador deve rejeitar Π. Por outro lado, segue do Teorema 22 que se uma das funções Ã, B̃, e C̃ não for δ-próxima a uma função linear, então a probabilidade de o teste correspondente no Teste de Linearidade falhar é maior que δ/2. Iterando-se este teste um número suficientemente grande de vezes, podemos aumentar esta probabilidade para qualquer θ < 1. Note que, desde que θ < 1 seja uma constante real fixa, basta iterar o teste acima um número O(1) de vezes.

Teorema 23. Seja 0 < δ < 1/3 uma constante fixa. Então existe um inteiro k = k(δ) ≥ 1 que depende apenas de δ para o qual vale o seguinte. Se não existem a ∈ 𝔽_{2}^{n}, b ∈ 𝔽_{2}^{n^{2}}, ou c ∈ 𝔽_{2}^{n^{3}} tais que as funções Ã e A, B̃ e B, e C̃ e C são δ-próximas, onde A(x) = ⟨a, x⟩ (x ∈ 𝔽_{2}^{n}), B(x) = ⟨b, y⟩ (y ∈ 𝔽_{2}^{n^{2}}), e C(z) = ⟨c, z⟩ (z ∈ 𝔽_{2}^{n^{3}}), então, iterando-se o Teste de Linearidade k vezes, a probabilidade de o teste falhar é de pelo menos 1 − δ.

3.1.6. O teste de consistência. Suponha agora que Ã, B̃, e C̃ passaram pelo Teste de Linearidade. Assim podemos assumir que existem funções lineares A, B, e C como no Teorema 23. Sejam a ∈ 𝔽_{2}^{n}, b ∈ 𝔽_{2}^{n^{2}}, e c ∈ 𝔽_{2}^{n^{3}} como naquele teorema. O nosso objetivo agora é verificar se estes vetores satisfazem o critério de consistência dado por (16). Como anteriormente, se x, x′ ∈ 𝔽_{2}^{n}, escrevemos x ∘ x′ para o vetor y = (y_{ij})_{1≤i,j≤n} com y_{ij} = x_{i}x_{j} (1 ≤ i, j ≤ n). Ademais, se y = (y_{jk})_{1≤j,k≤n} ∈ 𝔽_{2}^{n^{2}}, escrevemos x ∘ y para o vetor z = (z_{ijk})_{1≤i,j,k≤n} com coordenadas z_{ijk} = x_{i}y_{jk} (1 ≤ i, j, k ≤ n). Note agora que

A(x)A(x′) = B(x ∘ x′)  (21)

para todo x, x′ ∈ 𝔽_{2}^{n} se e só se b = a ∘ a, e que

A(x)B(y) = C(x ∘ y)  (22)

para todo x ∈ 𝔽_{2}^{n} e todo y ∈ 𝔽_{2}^{n^{2}} se e só se c = a∘b. As identidades (21) e (22) são candidatas naturais para a verificação da consistência entre os vetores a, b, e c. Naturalmente, um verificador (n^{3}, 1)-restrito não pode verificar estas identidades para todos os x, x′, e y. Entretanto, a seguinte observação é suficiente para se resolver este problema.

Lema 24. Suponha que A, B, e C são funções lineares dadas por a, b, e c como acima, mas que b ≠ a ∘ a e c ≠ a ∘ b. Então

ℙ_{x,x′}{A(x)A(x′) ≠ B(x ∘ x′)} ≥ 1/4,  (23)

onde x, x′ ∈_{R} 𝔽_{2}^{n}, e

ℙ_{x,y}{A(x)B(y) ≠ C(x ∘ y)} ≥ 1/4,  (24)

onde x ∈_{R} 𝔽_{2}^{n} e y ∈_{R} 𝔽_{2}^{n^{2}}.

Prova. Provemos (23). Por conveniência, considere a ∘ a ∈ 𝔽_{2}^{n^{2}} e b = (b_{ij}) ∈ 𝔽_{2}^{n^{2}} como matrizes n × n da forma natural. Temos assim A(x)A(x′) = ⟨x, (a ∘ a)x′⟩ e B(x ∘ x′) = ⟨x, bx′⟩ para quaisquer x, x′ ∈ 𝔽_{2}^{n}. Usando o fato de que dois funcionais lineares distintos sobre 𝔽_{2}^{n} concordam em exatamente metade dos pontos de 𝔽_{2}^{n}, temos do fato de que b ≠ a ∘ a que

ℙ_{x′}{(a ∘ a)x′ ≠ bx′} ≥ 1/2,

e também que

ℙ_{x}{⟨x, (a ∘ a)x′⟩ ≠ ⟨x, bx′⟩} = 1/2

para todo x′ ∈ 𝔽_{2}^{n} tal que (a ∘ a)x′ ≠ bx′. Daí segue (23). A desigualdade (24) segue de forma análoga. □

O uso do Lema 24 apresenta, entretanto, uma dificuldade. Lembre que não temos acesso às funções A, B, e C, mas às funções δ-próximas respectivas Ã, B̃, e C̃. Em particular, embora seja imediato que

ℙ_{x,x′}{A(x)A(x′) ≠ Ã(x)Ã(x′)} ≤ 2δ

para x, x′ ∈_{R} 𝔽_{2}^{n}, não podemos em geral afirmar que

ℙ_{x,x′}{B(x ∘ x′) ≠ B̃(x ∘ x′)} ≤ 2δ,

já que x ∘ x′ não é um elemento uniformemente distribuído em 𝔽_{2}^{n^{2}} quando x, x′ ∈_{R} 𝔽_{2}^{n}. Este problema pode ser contornado com o uso de funções ‘auto-corretoras’. Defina as funções aleatórias

SC-Ã: 𝔽_{2}^{n} → 𝔽_{2},  SC-B̃: 𝔽_{2}^{n^{2}} → 𝔽_{2},  SC-C̃: 𝔽_{2}^{n^{3}} → 𝔽_{2}

como dadas na Figura IV.9.

SC-Ã(x): Escolha r ∈_{R} 𝔽_{2}^{n}, e devolva Ã(x + r) − Ã(r).

SC-B̃(y): Escolha r ∈_{R} 𝔽_{2}^{n^{2}}, e devolva B̃(y + r) − B̃(r).

SC-C̃(z): Escolha r ∈_{R} 𝔽_{2}^{n^{3}}, e devolva C̃(z + r) − C̃(r).

Figura IV.9. As Funções Auto-Corretoras

A observação simples que torna estas funções importantes para nós é a seguinte. Lembre que Ã, B̃, e C̃ são δ-próximas às funções lineares A, B, e C.

Lema 25. Para todo x ∈ 𝔽_{2}^{n}, y ∈ 𝔽_{2}^{n^{2}}, e z ∈ 𝔽_{2}^{n^{3}}, temos

ℙ{ SC-Ã(x) = A(x)} ≥ 1 − 2δ, ℙ{ SC-B̃(y) = B(y)} ≥ 1 − 2δ,

e

ℙ{ SC-C̃(z) = C(z)} ≥ 1 − 2δ.

Naturalmente, as probabilidades no lema acima referem-se aos valores das funções aleatórias SC-Ã, SC-B̃, e SC-C̃. Note agora que se Ã, B̃, e C̃ são δ-próximas a A, B, e C com a, b, e c tais que b ≠ a ∘ a e c ≠ a ∘ b, então, pelos Lemas 24 e 25, temos que

ℙ_{x,x′}{ SC-Ã(x) SC-Ã(x′) ≠ SC-B̃(x ∘ x′)} ≥ 1/4 − 6δ

para x, x′ ∈_{R} 𝔽_{2}^{n}, e

ℙ_{x,y}{ SC-Ã(x) SC-B̃(y) ≠ SC-B̃(x ∘ y)} ≥ 1/4 − 6δ,

para x ∈_{R} 𝔽_{2}^{n}, y ∈_{R} 𝔽_{2}^{n^{2}}. A discussão acima sugere o teste de consistência para as aplicações lineares A, B, e C descrito na Figura IV.10.

(1) Escolha x, x′ ∈_{R} 𝔽_{2}^{n}, e verifique se SC-Ã(x) SC-Ã(x′) = SC-B̃(x ∘ x′).

(2) Escolha x ∈_{R} 𝔽_{2}^{n} e y ∈_{R} 𝔽_{2}^{n^{2}}, e verifique se SC-Ã(x) SC-B̃(y) = SC-C̃(x ∘ y).

Figura IV.10. O Teste de Consistência

Podemos agora enunciar formalmente o resultado que permite ao verificador executar os Passos 1 e 2 do processo de verificação.

Lema 26. Seja 0 < δ < 1/24 uma constante fixa. Então existe um inteiro k = k(δ) ≥ 1 que depende apenas de δ para o qual vale o seguinte. Se não existe a ∈ 𝔽_{2}^{n} tal que as funções Ã e A, B̃ e B, e C̃ e C são δ-próximas, onde A(x) = ⟨a, x⟩ (x ∈ 𝔽_{2}^{n}), B(x) = ⟨a ∘ a, y⟩ (y ∈ 𝔽_{2}^{n^{2}}), e C(z) = ⟨a ∘ a ∘ a, z⟩ (z ∈ 𝔽_{2}^{n^{3}}), então, iterando-se o Teste de Linearidade e o Teste de Consistência k vezes cada, a probabilidade de um destes testes falhar é de pelo menos 1 − δ.

(1) Escolha r ∈_{R} 𝔽_{2}^{n} e calcule c = c_{r}, S_{1} = S_{1}(r) ∈ 𝔽_{2}^{n}, S_{2} = S_{2}(r) ∈ 𝔽_{2}^{n^{2}}, e S_{3} = S_{3}(r) ∈ 𝔽_{2}^{n^{3}} como em (14).

(2) Verifique se c + Ã(S_{1}) + B̃(S_{2}) + C̃(S_{3}) = 0.

Figura IV.11. O Teste de Satisfatibilidade

3.1.7. O teste de satisfatibilidade. Resta-nos descrever o processo pelo qual executamos o Passo 3 do algoritmo de verificação. Este passo é, na verdade, bastante simples. Considere o procedimento dado na Figura IV.11.

O resultado formal que nos garante a ‘correção’ do Teste de Satisfatibilidade é o seguinte.

Lema 27. Seja 0 < δ < 1 uma constante fixa. Então existe um inteiro k = k(δ) ≥ 1 que depende apenas de δ para o qual vale o seguinte. Se a ∈ 𝔽_{2}^{n} é tal que C(a) ≠ 0, mas as funções Ã e A, B̃ e B, e C̃ e C são δ-próximas, onde A(x) = ⟨a, x⟩ (x ∈ 𝔽_{2}^{n}), B(x) = ⟨a∘a, y⟩ (y ∈ 𝔽_{2}^{n^{2}}), e C(z) = ⟨a∘a∘a, z⟩ (z ∈ 𝔽_{2}^{n^{3}}), então, iterando-se o Teste de Satisfatibilidade k vezes, a probabilidade de um destes testes falhar é de pelo menos 1 − δ.

Os Lemas 26 e 27 fornecem conjuntamente o seguinte resultado.

Teorema 28. Existe uma constante absoluta k ≥ 1 tal que a iteração do Teste de Linearidade, do Teste de Consistência, e do Teste de Satisfatibilidade k vezes cada, e aceitando φ se e só se nenhum destes testes detecta inconsistência na prova Π apresentada, constitui um verificador (n^{3}, 1)-restrito para 3sat.

Devido à NP-completude de 3sat, temos o seguinte resultado.

Corolário 29. NP ⊂ PCP(poly(n), 1).

3.1.8. Codificação de soluções. Por motivos técnicos, precisamos detalhar uma característica do verificador (n^{3}, 1)-restrito que descrevemos acima. A idéia aqui é a seguinte. A demonstração transparente Π_{φ} acima da satisfatibilidade de φ é uma seqüência que descreve as três funções lineares A, B, e C. Podemos pensar em A como sendo uma codificação do vetor a, que é por sua vez uma representação de uma atribuição que satisfaz φ. Será importante na Secão 3.3 abaixo pensar em A como uma codificação de uma ‘solução’ do problema de satisfazer φ, e em B e C como uma demonstração de que A é de fato uma tal codificação.

Formalmente, precisamos introduzir soluções probabilisticamente verificáveis. Dizemos que uma relação R ⊂ Σ^{∗} × Σ^{∗} é uma p-relação se (i) existe um polinômio p tal que |y| ≤ p(|x|) para todo (x, y) ∈ R, e (ii) o predicado ‘(x, y) ∈ R’ pode ser verificado em tempo polinomial em |x| + |y|. Para maiores detalhes, veja a discussão imediatamente após a Definição 5 do Capítulo II.^{1}

Por exemplo, seja

R_{3sat} = {(x, y) ∈ Σ^{∗} × Σ^{∗}: x é uma instância φ de 3sat codificada e

y codifica uma atribuição que satisfaz φ}.

Então R_{3sat} é uma p-relação.

Uma função E: Σ^{∗} → Σ^{∗} é uma codificação se o comprimento |E(x)| de E(x) depende apenas do comprimento |x| de x e, ademais, se E(x) e E(x′) diferem em no mínimo metade de seus caracteres sempre que |x| = |x′| mas x ≠ x′. Note que a aplicação

E_{0} : x ∈ Σ^{∗} ↦ (⟨x, y⟩: y ∈ 𝔽_{2}^{|x|}) ∈ Σ^{∗}  (25)

é uma codificação. Note ainda que na prova transparente Π_{φ} discutida acima, podemos identificar A com E_{0}(a).

Um verificador de soluções é um verificador que tem acesso não só a uma prova Π ∈ Σ^{∗}, mas também a uma solução s ∈ Σ^{∗}, que ele também acessa via um oráculo. Por motivos técnicos, será ainda necessário exigir que tanto a solução s como a prova Π fornecidas ao verificador de soluções venham segmentadas em blocos de algum comprimento fixo. Tais blocos devem ter início em posições que são congruentes a 1 módulo o comprimento dos blocos. Em outras palavras, tanto a solução s como a prova Π devem ser concatenações de segmentos de um comprimento fixo e, ademais, em cada acesso a s ou Π, o verificador recebe do oráculo um destes segmentos que constituem estas seqüências.

1Note que usamos aqui por conveniência uma terminologia levemente diferente.

Um verificador de soluções é dito ser (r(n), q(n), b(n))-restrito se existem funções inteiras r̂(n) = O(r(n)), q̂(n) = O(q(n)), e b̂(n) = O(b(n)) para as quais vale o seguinte. Com uma entrada x de comprimento n, o verificador usa no máximo r̂(n) bits aleatórios e acessa no total não mais que q̂(n) blocos da solução s e da prova Π, onde assumimos que ambos s e Π são segmentados com blocos de comprimento b̂(n). Novamente, o verificador é assumido ser não-adaptativo, isto é, uma vez definidas a entrada x e a seqüência aleatória τ, os blocos de s e Π a serem lidos ficam determinados, independentemente da solução s e da prova Π apresentadas. Seja V (x, τ, s, Π) ∈ {aceita, rejeita} a saída do nosso verificador de soluções quando a entrada é x, a seqüência de bits aleatórios é τ, a solução é s, e a prova é Π.

Definição 30. Seja R ⊂ Σ^{∗} × Σ^{∗} uma p-relação e E: Σ^{∗} → Σ^{∗} uma codificação. Então o par (R, E) pertence a PCS(r(n), q(n), b(n)) se e só se existe um verificador de soluções (r(n), q(n), b(n))-restrito V tal que

(i) Para todo x, y ∈ Σ^{∗} com (x, y) ∈ R, existe uma prova Π_{x,y} ∈ Σ^{∗} tal que

ℙ_{τ} {V (x, τ, E(y), Π_{x,y}) = aceita} = 1.  (26)

(ii) Para todo x e s ∈ Σ^{∗} tal que s não é 1/4-próximo a uma codificação E(y) de algum y ∈ R(x), temos

ℙ_{τ} {V (x, τ, s, Π) = aceita} < 1/4  (27)

para todo Π ∈ Σ^{∗}.

O seguinte teorema segue imediatamente das discussões desta seção.

Teorema 31. Seja E_{0} : Σ^{∗} → Σ^{∗} a codificação dada em (25). Então

(R_{3sat}, E_{0}) ∈ PCS(n^{3}, 1, 1).

Finalmente, note que o seguinte resultado segue de uma rápida comparação das definições.

Lema 32. Seja R ⊂ Σ^{∗} × Σ^{∗} uma p-relação e E: Σ^{∗} → Σ^{∗} uma codificação. Seja L ⊂ Σ^{∗} a linguagem naturalmente dada por R, de forma que x ∈ L se e só se R(x) ≠ ∅. Então se

(R, E) ∈ PCS(r(n), q(n), b(n)),

temos que L ∈ PCP(r(n), q(n)b(n)).

3.2. Certificados transparentes II. As técnicas de que fizemos uso na Seção 3.1 ilustram vários ingredientes da demonstração do Teorema 18. Entretanto, a codificação E_{0}, em que se baseiam todos os resultados principais daquela seção, tem um defeito fundamental: o comprimento de E_{0}(x) é exponencial no comprimento de x. Desta forma, para interpretar soluções codificadas por E_{0}, qualquer verificador precisa de um número polinomial de bits aleatórios.

Na demonstração do Teorema 18, Arora et al. usam além de E_{0} uma outra codificação, uma codificação polinomial e não apenas linear como E_{0}. Esta codificação, E_{1}, já havia sido utilizada com sucesso em trabalhos anteriores de Arora e Safra [AS92b] e outros (veja as notas bibliográficas abaixo). A codificação E_{1} : Σ^{∗} → Σ^{∗} é muito mais ‘econômica’ na quantidade de bits aleatórios que são necessários, embora eles sejam razoavelmente custosos em termos do número de caracteres da solução e da prova que precisam ser examinados. Esta codificação E_{1} é tal que se temos uma instância satisfatível φ de 3sat e a ∈ 𝔽_{2}^{n} satisfaz φ, então E_{1}(a) tem comprimento O(n^{3}).

Como mencionado acima, enquanto que E_{0} é uma codificação baseada em funcionais lineares, E_{1} é baseada em codificações polinomiais. Os resultados algébricos envolvidos no estudo de E_{1} são mais sofisticados, embora ainda elementares. Não entraremos em detalhes aqui; restringiremo-nos a enunciar dois resultados principais sobre E_{1}. O primeiro é o seguinte.

Teorema 33. (R_{3sat}, E_{1}) ∈ PCS(log n, 1, poly(log n)).

Introduzimos agora uma notação para que possamos enunciar o segundo resultado sobre E_{1}. Seja q um inteiro positivo. A codificação E_{1}^{(q)} : (Σ^{q})^{∗} → Σ^{∗} é definida por

E_{1}^{(q)}(x) = E_{1}(x_{1}) … E_{1}(x_{q})  (28)

para todo x = x_{1} … x_{q}, onde |x_{1}| = ⋯ = |x_{q}|. Note que, estritamente falando, não devemos nos referir a E_{1}^{(q)} como uma codificação, já que ela não está definida para x ∈ Σ^{∗} de comprimento não divisível por q. Entretanto, como estaremos sempre codificando atribuições a ∈ 𝔽_{2}^{n} que satisfazem uma dada instância φ de 3sat, podemos assumir que o número de variáveis n em φ é divisível por qualquer inteiro q dado de antemão. O segundo resultado principal sobre E_{1} é o seguinte.

Teorema 34. Para todo inteiro positivo q, temos

(R_{3sat}, E_{1}^{(q)}) ∈ PCS(log n, 1, poly(log n)).

A demonstração do Teorema 18 usará basicamente apenas estes dois resultados sobre E_{1}. Apenas para completude, enunciamos o resultado abaixo, que é um lema intermediário na demonstração do Teorema 33. Note por outro lado que o Lema 32 diz que o resultado abaixo segue imediatamente do Teorema 33.

Corolário 35. NP ⊂ PCP(log n, poly(log n)).

Terminamos esta seção enunciando um resultado sobre E_{0} no mesmo espírito do Teorema 34. Defina E_{0}^{(q)} : (Σ^{q})^{∗} → Σ^{∗} de forma análoga à definição de E_{1}^{(q)}. Temos então a seguinte generalização do Teorema 31.

Teorema 36. Para todo inteiro positivo q, temos

(R_{3sat}, E_{0}^{(q)}) ∈ PCS(n^{3}, 1, 1).

3.3. Provas transparentes recursivas. Aqui completamos a demonstração do Teorema 18. Os ingredientes principais serão os Teoremas 31, 33, 34, e 36. A idéia fundamental é que é possível combinar características de E_{0} e E_{1} através de uma codificação ‘recursiva’. Suponha que, como acima, temos uma instância satisfatível φ de 3sat, e que a ∈ 𝔽_{2}^{n} satisfaz φ.

Lembremos o que significa o Teorema 33. Ponha s = E_{1}(a). Aquele teorema diz que há uma prova Π ∈ Σ^{∗} tal que as seguintes afirmativas são válidas. Tanto s quanto Π são segmentados, com cada segmento de comprimento b̂(n) = O(poly(log n)). Ademais, existe um verificador de soluções V que usa r̂(n) = O(log n) bits aleatórios, e acessa q̂(n) = O(1) blocos de s e de Π para decidir se aceita ou não φ.

Suponha que a seqüência de bits aleatórios τ é fornecida ao nosso verificador V. Dado que os blocos a serem lidos dependem apenas de φ e de τ, podemos assumir neste ponto que V simplesmente aceita ou rejeita φ com base nos q̂(n) = O(1) blocos de s e Π a serem lidos. Esta discussão mostra que a saída de V, após fixo τ, é simplesmente computada por uma máquina de Turing determinística M_{τ} = M_{τ,φ} com base em uma entrada segmentada π = π_{τ} = π_{1} … π_{q}, onde q = q̂(n) = O(1) e |π_{i}| = b̂(n) = O(poly(log n)) para todo 1 ≤ i ≤ q.

Precisamos agora recordar um teorema clássico de Cook [Coo71].

Teorema 37. Seja M uma máquina de Turing de complexidade de tempo polinomial. Então existem polinômios p_{1}(n) e p_{2}(n) e uma máquina de Turing determinística M′ para os quais vale o seguinte. Para todo inteiro n ≥ 0, a máquina M′ computa em tempo no máximo p_{1}(n) uma instância

Φ(y, z) = Φ_{M}(y, z)

de 3sat com variáveis y = (y_{1}, …, y_{n}) e z = (z_{1}, …, z_{p_{2}(n)}) tal que M aceita a entrada x = x_{1} … x_{n} ∈ Σ^{∗} se e só a fórmula booleana Ψ(z) = Ψ_{x}(z) = Φ(x, z) obtida a partir de Φ(y, z) pondo-se y = x é satisfatível.

Seja Φ_{τ}(y, z) = Φ_{τ,φ}(y, z) a instância de 3sat dada pelo teorema de Cook para a nossa máquina M_{τ} = M_{τ,φ} acima. Sabemos que V aceitará φ se e só se M_{τ} aceita π = π_{τ}. Pela definição de Φ_{τ}(y, z), isto ocorre se e só se Ψ_{τ}(z) = Φ_{τ}(π_{τ}, z) é satisfatível. Sem perda de generalidade, podemos assumir que |z| = b̂(n). Como estamos admitindo que φ é satisfatível, sabemos que Ψ_{τ}(z) = Φ_{τ}(π_{τ}, z) é satisfatível, e podemos assim incorporar na nossa prova transparente de que φ é satisfatível uma prova transparente de que, para todo τ, a fórmula booleana Ψ_{τ}(z) = Φ_{τ}(π_{τ}, z) é satisfatível.

Para tanto, usamos E_{1}^{(q+1)} para codificar

(π, z_{0}) = (π_{τ}, z_{0}) = (π_{1}, …, π_{q}; z_{0}),

onde z_{0} é tal que Ψ_{τ}(z_{0}) = Φ_{τ}(π_{τ}, z_{0}) = V, e invocamos o Teorema 34 para obter uma prova transparente Π = Π_{τ} do fato de que

E_{1}^{(q+1)}(π_{τ}, z_{0}) = (E_{1}(π_{1}), …, E_{1}(π_{q}); E_{1}(z_{0}))  (29)

codifica realmente uma solução para a instância Ψ_{τ}(z) = Φ_{τ}(π_{τ}, z) de 3sat. Note que o número de variáveis na fórmula booleana Ψ_{τ}(z) = Φ_{τ}(π_{τ}, z) é apenas O(poly(log n)). Assim, o Teorema 34 garante que existe um verificador para interpretar (29) que é

(log log n, 1, poly(log log n))-restrito.

A formalização das idéias acima, que exige certas observações técnicas adicionais não mencionadas, fornece a seguinte versão refinada do Teorema 33.

Teorema 38. (R_{3sat}, E_{1}) ∈ PCS(log n, 1, poly(log log n)).

Note que o resultado acima foi obtido, essencialmente, ‘compondose’ E_{1} recursivamente e usando os Teoremas 33 e 34. Compondose agora E_{1} com E_{0} e usando os Teoremas 38 e 36, completamos a demonstração do Teorema 18.

De fato, agora usamos E_{0} para codificar as soluções das instâncias Ψ_{τ}(z) = Φ_{τ}(π_{τ}, z) de 3sat acima e, devido ao Teorema 38, podemos agora assumir que a variável z tem comprimento poly(log log n). O Teorema 36 fornece então um verificador que usa poly(log log n) bits aleatórios apenas, e examina somente uma quantidade O(1) de entradas da solução e da prova apresentadas. Podemos concluir portanto que

(R_{3sat}, E_{1}) ∈ PCS(log n, 1, 1).

Claramente, basta agora usar o fato de que 3sat é NP-completo e o Lema 32 para concluir que NP ⊂ PCP(log n, 1). Isto completa a demonstração do Teorema 18.

4. Notas Bibliográficas

O sistema de provas PCP foi introduzido por Arora e Safra [AS92b], e este trabalho foi imediatamente seguido pelo resultado definitivo de Arora, Lund, Motwani, Sudan, e Szegedy [ALM^{+}92b]. Mais amplamente falando, a linha de pesquisa destes trabalhos foi sugerida por vários resultados na área de provas interativas (cf. Capítulo III). Em particular, a investigação do poder de sistemas interativos que contam com vários provadores foi importante. Dois resultados maximais sobre estes sistemas são devidos a Feige e Lovász [FL92] e Bellare, Goldwasser, Lund, e Russel [BGLR93, BGLR94]. Para uma ótima discussão sobre estes sistemas e a sua relação com os sistemas PCP, veja Babai [Bab94].

Os resultados que foram sucessivamente refinados até a obteção do Teorema 18 são devidos a Babai, Fortnow, e Lund [BFL91], Babai, Fortnow, Levin, e Szegedy [BFLS91], Feige, Goldwasser, Lovász, Safra, e Szegedy [FGL^{+}91], e Arora e Safra [AS92b]. Em particular, Arora et al. [ALM^{+}92b] atribuem o Teorema 33 ao conjunto destes trabalhos. A técnica de composição de codificações e dos respectivos verificadores (cf. Seção 3.3 acima) é devida a Arora e Safra [AS92b] e a Arora, Lund, Motwani, Sudan, e Szegedy [ALM^{+}92b].

Os Teoremas 31 e 36 são devidos a Arora et al. [ALM^{+}92b], e tiveram origem em resultados anteriores sobre verificação de programas e auto-correção [BLR90, Lip91]. O Teorema 22 é devido a Blum, Luby, e Rubinfeld [BLR90]. Funções auto-corretoras e, mais genericamente, a idéia de que programas podem verificar seus próprios resultados são o assunto de Blum e Kannan [BK89], Lipton [Lip91], e Blum, Luby, e Rubinfeld [BLR90].

Além dos artigos originais [ALM^{+}92a, ALM^{+}92b], trabalhos que contém provas completas do Teorema 18 incluem, entre outros, Sudan [Sud92], Arora [Aro94], e Hougardy, Prömel, e Steger [HPS94]. Este capítulo deve muito à excelente exposição de Hougardy, Prömel, e Steger [HPS94].

CAPÍTULO V COMPLEXIDADE DE PROBLEMAS DE APROXIMAÇÃO

Nas classes P e NP são colocados problemas de decisão, ou seja, problemas com resposta sim ou não. Em conexão com alguns problemas de decisão, aparecem os ‘problemas de otimização.’

Um problema de otimização P é um problema ou de maximização ou de minimização e consiste de três partes:

(1) um conjunto I de instâncias de P;

(2) para cada instância x ∈ I, um conjunto finito S(x) de candidatos à solução para x;

(3) uma função m que atribui a cada instância x ∈ I e cada candidato à solução y ∈ S(x) um número racional positivo m(x, y), chamado de valor do candidato à solução y.

Se P é um problema de minimização (resp., maximização), então uma solução ótima para uma instância x ∈ I é um candidato y^{∗} ∈ S(x) tal que, para todo y ∈ S(x), temos m(x, y^{∗}) ≤ m(x, y) (resp., m(x, y^{∗}) ≥ m(x, y)). Usaremos a notação OTIM(x) para denotar o valor m(x, y^{∗}) de uma solução ótima para x.

Por exemplo, o problema de otimização Max-3sat relacionado com o Problema 3sat é o de encontrar uma atribuição que maximize o número de cláusulas satisfeitas. O problema de otimização relacionado com o Problema Circuito Hamiltoniano poderia ser o de encontrar no grafo dado um circuito, não necessariamente hamiltoniano, mas contendo o maior número possível de vértices. A outros problemas, porém, não correspondem problemas de otimização.

Para os problemas de otimização, faz sentido pensarmos em soluções aproximadas. Uma solução aproximada é um candidato à solução cujo valor não é muito diferente do valor ótimo.

Definição 39. Seja P um problema de otimização, x uma instância de P e y um candidato à solução para x. A razão de aproximação de y em relação a x é definido por

R(x, y) = max \{\frac{m(x, y)}{OTIM(x)}, \frac{OTIM(x)}{m(x, y)}\} .

Note que de acordo com essa definição a razão de aproximação é sempre maior ou igual a 1.

Definição 40. Seja A um algoritmo para um problema P que, dada uma instância x, devolve um candidato à solução A(x). Seja r uma função r: ℕ → [1, ∞). Dizemos que A obtém grau de aproximação r para P se, para toda instância x,

R(x, A(x)) ≤ r(|x|).

Note que de acordo com essa definição a função r somente pode assumir valores maiores ou iguais a 1. Por simplicidade, um algoritmo como na definição acima é dito aproximar o problema P com razão r

1. As Classes NPO, APX e EAP

O sentido deste estudo de aproximabilidade é o de investigar como se comportam problemas NP-completos quando, ao invés de buscarmos uma resposta sim ou não, estamos interessados em soluções aproximadas. A definição a seguir captura essa noção: ao invés de considerarmos problemas de otimização em geral, vamos nos concentrar em problemas de otimização que tenham características de problemas em NP.

Definição 41. Um problema de otimização P está na classe NPO se as seguintes condições são satisfeitas:

(1) o conjunto das instâncias de P é reconhecível em tempo polinomial no tamanho da instância;

(2) para x uma instância de P, o problema de pertinência ao conjunto dos candidatos à solução de x é solúvel em tempo polinomial em |x|; (3) dados uma instância x e um candidato y à solução de x, o

valor m(x, y) de y é computável em tempo polinomial.

Durante todo este capítulo, todo problema de otimização deve ser entendido como um problema em NPO.

Definição 42. Um problema P em NPO está na classe APX se existe algum ε > 0 para o qual existe um algoritmo polinomial que aproxime o problema com grau de aproximação r ≤ 1 + ε.

Definição 43. Dizemos que P em NPO tem um esquema de aproximação polinomial, se para cada ε > 0 existe um algoritmo polinomial A_{ε} que aproxime P com grau de aproximação r ≤ 1+ε. Dizemos que P está na classe EAP se ele tem um esquema de aproximação polinomial.

Pelas definições, trivialmente temos que EAP ⊆ APX ⊆ NPO. Vamos mostrar que todas as inclusões são próprias, a menos que P = NP, o que tornaria as três classe iguais.

O exemplo clássico de um problema em EAP cujo problema de decisão correspondente é NP-completo (veja Secão 2), é o Problema Mochila Máxima. A prova deste teorema se encontra na Seção 4.

Teorema 44. O Problema Mochila Máxima está em EAP.

Vamos mostrar mais a frente (Teorema 67), que o Problema Max-3sat não está em EAP, a menos que P = NP. Provamos também na Seção 4 o seguinte teorema.

Teorema 45. O Problema Max-3sat está em APX.

Finalmente, o Problema Clique Máximo, que claramente está em NPO, não pode estar em APX, a menos que P = NP. É o que mostramos no Teorema 68. (Este resultado é, na verdade, bastante mais forte.)

2. Completude para Classes de Complexidade

O conceito de problemas completos é bastante importante nas classes de complexidade. Por um lado mostra-se que existem problemas completos na classe, isto é, problemas que são tão difíceis quanto qualquer outro da mesma classe. Isso implica que, havendo uma melhora substancial no método de solução de um problema completo, esse método pode se estender a todos os outros problemas da classe. Por outro lado, estabelecem-se métodos, chamados de reduções, para se transformar um problema em outro. Essas reduções objetivam caracterizar outros problemas da classe como completos, ou mesmo caracterizar problemas como tão difíceis quanto qualquer problema da classe. Por exemplo, se um problema P_{1} é completo e pode ser convenientemente reduzido a um problema P_{2}, então o problema P_{2}, se pertencer à classe, também é completo.

Nesta seção definimos e exemplificamos tais conceitos.

2.1. Classe NP. Definimos a seguir uma redução conveniente para problemas da classe NP, conhecida como redução de Karp.

Definição 46. Uma redução de Karp de uma linguagem L_{1} ∈ Σ_{1}^{∗} para uma linguagem L_{2} ∈ Σ_{2}^{∗} é uma função f: Σ_{1}^{∗} → Σ_{2}^{∗} computável em tempo polinomial tal que para qualquer x ∈ Σ_{1}^{∗},

x ∈ L_{1} ⇔ f(x) ∈ L_{2}.

Usamos a notação L_{1} ≤_{Karp} L_{2} para denotar a existência de uma redução de Karp de L_{1} para L_{2}. A propriedade fundamental de uma redução de Karp é que se L_{1} ≤_{Karp} L_{2} e existe um algoritmo polinomial para decidir o problema de pertinência em L_{2}, o problema de pertinência em L_{1} pode ser resolvido em tempo polinomial usando o algoritmo para L_{2} e a função f.

Definição 47. Uma linguagem L é NP-completa se L ∈ NP e para qualquer L′ ∈ NP, temos L′ ≤_{Karp} L.

O mesmo conceito é importante para a classe coNP.

Definição 48. Uma linguagem L é coNP-completa se L ∈ coNP e para qualquer L′ ∈ coNP, temos L′ ≤_{Karp} L.

2. COMPLETUDE PARA CLASSES DE COMPLEXIDADE 71

Os teoremas a seguir, típicos em teoria da complexidade, são aplicações dos conceitos dados acima e consistem de resultados clássicos para a classe NP.

Teorema 49. Se L_{1} ≤_{Karp} L_{2} e L_{2} ≤_{Karp} L_{3}, então L_{1} ≤_{Karp} L_{3}.

Teorema 50. Se L_{1} ≤_{Karp} L_{2} e L_{2} ∈ P, então L_{1} ∈ P.

Teorema 51. Se L_{1} é NP-completa, L_{2} ∈ NP, e L_{1} ≤_{Karp} L_{2}, então L_{2} é NP-completa.

Teorema 52. Se uma linguagem NP-completa está em P, então

P = NP .

Teorema 53. Os seguintes problemas são NP-completos.

(1) 2sat.

(2) 3sat.

(3) Satisfatibilidade.

(4) Clique.

(5) Circuito Hamiltoniano.

(6) Coloração.

(7) Passeio do Caixeiro Viajante.

(8) Mochila.

(9) Corte em Grafos.

(10) Árvore de Steiner.

A seguir damos o conceito de linguagens difíceis. Note que uma linguagem classificada como difícil para uma classe não precisa necessariamente estar na classe.

Definição 54. Uma linguagem L é NP-difícil se para qualquer L′ ∈ NP, temos L′ ≤_{Karp} L.

Equivalentemente, uma linguagem L é NP-difícil se para alguma linguagem NP-completa L′, temos L′ ≤_{Karp} L.

2.2. Classes APX e EAP. Embora a redução de Karp seja apropriada para problemas em NP, elas nada nos diz em relação à aproximação de problemas de otimização, pois a redução de Karp não necessariamente preserva soluções aproximadas. Portanto, para as classes APX e EAP vamos definir a L-redução (L de linear), redução esta que preserva aproximabilidade.

Definição 55. Uma L-redução de um problema de otimização P_{1} para um problema de otimização P_{2} é uma quádrupla (f, g, α, β) de dois algoritmos polinomiais f e g e duas constantes α, β > 0 satisfazendo as seguintes condições:

(1) Para toda instância x_{1} de P_{1}, x_{2} = f(x_{1}) é uma instância de P_{2} satisfazendo OTIM_{P_{2}}(x_{2}) ≤ α OTIM_{P_{1}}(x_{1}).

(2) Para todo y_{2}, candidato à solução de x_{2} com c_{2} = m_{P_{2}}(x_{2}, y_{2}), y_{1} = g(y_{2}) é um candidato à solução de x_{1} com c_{1} = m_{P_{1}}(x_{1}, y_{1}) satisfazendo

|c_{1} − OTIM(x_{1})| ≤ β|c_{2} − OTIM(x_{2})|.

Usamos a notação P_{1} ≤_{L} P_{2} para denotar a existência de uma Lredução de P_{1} para P_{2}. A L-redução é ilustrada na Figura V.12.

Definição 56. Um problema de otimização P é APX-completo se P ∈ APX e para qualquer P′ ∈ APX, vale que P′ ≤_{L} P.

Os teoremas a seguir são os equivalentes, para a classe APX, aos vistos na seção anterior para a classe NP. Em todos os teoremas abaixo, estamos supondo que os P_{i} são problemas de otimização que pertencem à classe NPO.

Teorema 57. Se P_{1} ≤_{L} P_{2} e P_{2} ≤_{L} P_{3}, então P_{1} ≤_{L} P_{3}.

Teorema 58. Se P_{1} ≤_{L} P_{2} e P_{2} ∈ EAP, então P_{1} ∈ EAP.

Teorema 59. Se P_{1} ≤_{L} P_{2} e P_{2} ∈ APX, então P_{1} ∈ APX. Mais precisamente, se existe um algoritmo polinomial A para P_{2} com grau de aproximação r_{A} ≤ 1 + ε, então existe um algoritmo polinomial B para P_{1} com grau de aproximação r_{B} ≤ 1 + αβε.

Teorema 60. Se P_{1}, P_{2} ∈ APX, P_{1} é APX-completo e P_{1} ≤_{L} P_{2}, então P_{2} é APX-completo.

[figure: P_{1}; P_{2}; f; x_{1}; x_{2}; S(x_{1}); S(x_{2}); g; y_{1}; y_{2}]

Figura V.12. L-redução

Teorema 61. Se P_{1} ≤_{L} P_{2}, P_{1} é APX-completo e P_{2} ∈ EAP, então EAP = APX.

Veremos na Seção 3 que, a menos que P = NP, temos EAP ≠ APX.

Teorema 62. Os seguintes problemas são APX-completos.

(1) Max-sat.

(2) Max-2sat.

(3) Max-3sat.

(4) Corte Máximo.

(5) k-coloração Máxima.

(6) Super String Mínimo.

(7) Árvore Mínima de Steiner.

Definição 63. Um problema de otimização P é APX-difícil se para qualquer P′ ∈ APX, temos P′ ≤_{L} P.

Equivalentemente, um problema de otimização P é APX-difícil se para algum problema APX-completo P′, temos P′ ≤_{L} P.

3. Resultados de Inaproximabilidade

Quando queremos mostrar que um problema de decisão P é intratável computacionalmente, mostramos que ele é NP-completo ou NP-difícil. Como não se acredita que tais problemas possam ser resolvidos em tempo polinomial nos modelos computacionais convencionais, isso é uma evidência de que P é intratável computacionalmente. Para se provar que P é intratável, mostra-se que P′ ≤_{Karp} P para algum P′ NP-completo. A partir dos anos 70 proliferaram na literatura provas com esse estilo. Mas essas construções raramente preservavam aproximabilidade. Ou seja, se construíssemos um algoritmo polinomial que obtivesse uma solução aproximada, digamos, com um grau de aproximação de 11/10 para o problema de otimização relacionado com P, em geral nada podemos afirmar sobre a obtenção de uma solução aproximada para P′.

Logo após o aparecimento dos conceitos das classes P e NP, já se sabia que a obtenção de soluções aproximadas para problemas de otimização relacionados com alguns problemas NP-completos é computacionalmente tão difícil quanto a obtenção da solução exata. Para exemplificar, citamos os seguintes teoremas.

Teorema 64. Se P ≠ NP, então não existe um algoritmo polinomial para o Problema Coloração Mínima com grau de aproximação menor que 2.

Teorema 65. Se P ≠ NP, então não existe um algoritmo polinomial para o Problema Passeio do Caixeiro Viajante Mínimo com grau de aproximação menor que ∞.

Os teoremas acima mostram em particular que o Problema Coloração Mínima não pode estar em EAP, e o Problema Passeio do Caixeiro Viajante Mínimo não pode estar em APX, a menos que P = NP.

Para outros problemas, resultados similares aparecem de forma isolada, indicando a impossibilidade de certas aproximações. Em 1989, Papadimitriou e Yannakakis [PY88] definem duas classes para problemas de otimização: as classes MAXNP e MAXSNP. Eles definem reduções entre problemas de otimização e provam a existência de problemas completos para a classe MAXSNP. A característica dessas classes é que se existir um algoritmo polinomial que obtenha uma solução arbitrariamente próxima da solução ótima de um problema completo para uma das classes, esse algoritmo pode ser usado para obter aproximações arbitrariamente próximas do ótimo para todos os outros problemas nessa classe.

Em 1992, como corolário dos resultados relativos a provas verificáveis probabilisticamente, Arora et al. [ALM^{+}92b] mostram que os problemas completos para a classe MAXSNP não podem ser arbitrariamente aproximados, a menos que P = NP.

Mais recentemente, Ausiello, Crescenzi e Protasi [ACP94] definem de forma diferente classes de problemas de aproximação que se mostram equivalentes às mencionadas acima. Essas definições são as que estamos usando nestas notas.

3.1. Resultados negativos para a classe APX. Iremos mostrar que, a menos que P = NP, nenhum problema APX-difícil pode ter um esquema de aproximação polinomial e, portanto, não pode pertencer à classe EAP. Uma conseqüência desse fato é que, para cada problema APX-difícil P, existe uma constante ε > 0 tal que, a menos que P = NP, nenhum algoritmo polinomial para P pode obter grau de aproximação menor que 1 + ε. O teorema é o seguinte.

Teorema 66. A menos que P = NP, temos APX ≠ EAP.

Para provar o teorema, basta mostrar que, a menos que P = NP, existe um problema em APX que não pode pertencer a EAP. O problema apropriado para esse objetivo é o Max-3sat. A parte crucial da prova usa o resultado principal discutido no Capítulo IV, ou seja, que PCP(log n, 1) = NP.

Teorema 67. Não existe um esquema de aproximação polinomial para Max-3sat, a menos que P = NP.

Prova. Seja L ⊆ Σ^{∗} uma linguagem em NP. Vamos mostrar que, dado um esquema de aproximação polinomial para Max-3sat, o problema de pertinência para a linguagem L pode ser resolvido em tempo polinomial. Como a prova vale para qualquer L ∈ NP, decorre que P = NP.

Do Teorema 18 temos que existe um verificador (log n, 1)-restrito V para L. Dado x ∈ Σ^{∗} vamos descrever como construir em tempo polinomial uma instância S_{x} para Max-3sat tal que

x ∈ L ⇒ S_{x} é satisfatível
x ∉ L ⇒ \{ \begin{matrix}somente uma fração constante \\ (independente de x) das cláusulas \\ de S_{x} pode ser satisfeita. \end{matrix}

Com isso, fica fácil mostrar que se existe um esquema de aproximação polinomial para Max-3sat, então podemos decidir a pertinência de x em L e segue que P = NP.

Lembre-se de que no esquema PCP(log n, 1) o verificador V usa o oráculo um número constante de vezes para acessar a prova. A cada seqüência de bits aleatórios τ com |τ| = r̂(x) = O(log n), usada pelo verificador, corresponde um conjunto de endereços na prova. Para cada um desses endereços, vamos associar uma variável booleana da seguinte forma: para o endereço i associe a variável booleana b_{i}. Vamos considerar que cada prova Π corresponde à uma atribuição às variáveis b_{i}: o valor V é atribuído à variável b_{i} se o i-ésimo bit de Π for 1; o valor F é atribuído a b_{i} se o i-ésimo bit for 0. Para cada um dos 2^{|τ|} = 2^{r̂(x)} = 2^{O(log n)} possíveis valores de τ, seja S_{τ} a fórmula booleana com variáveis b_{i} que expressa quais Π são aceitos por V quando a entrada é x. Note que S_{τ} tem tamanho constante pois somente um número constante de bits de Π são acessados. Seja S′_{τ} a fórmula booleana S_{τ} expressa com no máximo 3 variáveis por cláusula^{1} (i.e., na forma 3sat). Como cada S′_{τ} tem tamanho constante, cada S′_{τ} tem um número constante, digamos ≤ k, de cláusulas. Seja S_{x} o conjunto de todas as cláusulas S′_{τ}. Pela definição de sistemas PCP temos que

x ∈ L ⇒ ∃Π_{x} tal que S_{x} é satisfatível
x ∉ L ⇒ ∀Π no máximo 1/4 das S′_{τ} são

satisfeitas simultaneamente.

1É fato bem conhecido que qualquer fórmula pode ser expressa, a custa de um certo aumento do número de variáveis e cláusulas, como a conjunção de cláusulas com no máximo 3 variáveis por cláusula. Veja Fatos 74 e 75.

Como cada S′_{τ} tem no máximo k cláusulas, segue que no caso de x ∉ L no máximo

1 − \frac{3}{4k}

das cláusulas de S_{x} são satisfeitas simultaneamente.

Se nos fosse dado um esquema de aproximação polinomial para Max-3sat, poderíamos obter um algoritmo polinomial para o problema com grau de aproximação menor que

(1 − \frac{3}{4k} )^{−1} = \frac{4k}{4k − 3}.

Observando que k é uma constante que não depende de x, com esse algoritmo poderíamos separar o caso em que x ∈ L do caso em que x ∉ L. No primeiro caso S_{x} é satifatível e o algoritmo nos devolveria uma atribuição satisfazendo mais do que 1 − 3/4k das cláusulas de S_{x}. No segundo caso no máximo 1 − 3/4k das cláusulas de S_{x} podem ser satisfeitas simultaneamente. □

3.2. A impossibilidade de se aproximar o clique máximo. O resultado da seção anterior tira a esperança de encontrarmos esquemas polinomiais de aproximação para vários problemas de otimização. Porém, outras conseqüências podem ser tiradas do fato que PCP(log n, 1) = NP. É o caso do seguinte teorema extremamente forte que iremos provar.

Teorema 68. Existe um ε > 0 para o qual o Problema Clique Máximo não pode ser aproximado em tempo polinomial com grau de aproximação menor que n^{ε}, onde n é o número de vértices do grafo dado, a menos que P = NP.

Antes de provar esse teorema, provaremos uma versão mais fraca.

Teorema 69. O Problema Clique Máximo não pode ser aproximado em tempo polinomial com grau de aproximação menor que 4, a menos que P = NP.

Prova. Como de costume, para um grafo G, denote por ω(G) a cardinalidade de um clique máximo de G. Seja L uma linguagem em NP sobre um alfabeto Σ. Fixe x ∈ Σ^{∗} com |x| = n. Vamos mostrar como construir eficientemente um grafo G_{x} e uma função f tais que

x ∈ L ⇒ ω(G_{x}) = f(n)  (30)
x ∉ L ⇒ ω(G_{x}) < \frac{1}{4}f(n).  (31)

Então, um algoritmo para o Problema Clique Máximo com grau de aproximação 4 pode ser usado para decidir pertinência em L.

Do Teorema 18 temos que existe um verificador (log n, 1)-restrito V para L. Seja r̂(n) = O(log n) o número de bits aleatórios usados por V e q̂(n) = O(1) o número de consultas feitas às provas. Considere o vetor (τ, b_{1}, b_{2}, …, b_{q̂(n)}), onde τ é uma seqüência de r̂(n) bits e cada b_{i} ∈ {0, 1} para todo i. Definimos como o conjunto de vértices de G_{x} os vetores (τ, b_{1}, b_{2}, …, b_{q̂(n)}) tais que se V usa τ como os bits aleatórios e recebe, como respostas às q̂(n) consultas à prova, os bits b_{1}, b_{2}, …, b_{q̂(n)}, então V aceita x. Dois vértices

v_{1} = (τ, b_{1}, b_{2}, …, b_{q̂(n)}) e v_{2} = (τ′, b′_{1}, b′_{2}, …, b′_{q̂(n)})

são adjacentes se existir uma prova Π consistente com v_{1} e v_{2}. Ou seja, se b_{i} e b′_{j} corresponderem a um mesmo bit consultado, então b_{i} = b′_{j}.

Vamos estimar |V (G_{x})|, o número de vértice de G_{x}. Como existem 2^{r̂(n)} possíveis τ, e para cada um deles 2^{q̂(n)} possíveis valores para os b_{i}, temos que |V (G_{x})| ≤ 2^{r̂(n)}2^{q̂(n)} = 2^{O(log n)+O(1)}, o que é polinomial em n. Para saber se um candidato a vértice é realmente um vértice em G_{x}, basta verificar se V aceita x usando a informação contida no candidato a vértice. Isso pode ser feito em tempo polinomial simulando-se o procedimento de verificação que V executa. Como podemos também verificar facilmente se dois vértices são adjacentes, segue que podemos construir G_{x} em tempo polinomial.

Fixe uma prova Π qualquer. Então,

ω(G_{x}) ≥ |{τ: V (x, τ, Π) = aceita}|
= 2^{r̂(n)}ℙ_{τ}(V (x, τ, Π) = aceita).

Por outro lado, se C é um clique em G_{x} então existe uma prova Π consistente com todos os vértices de C. Em particular, existe uma prova Π_{0} consistente com um clique de tamanho ω(G_{x}). Portanto,

ω(G_{x}) ≤ |{τ: V (x, τ, Π_{0}) = aceita}|
= 2^{r̂(n)}ℙ_{τ}(V (x, τ, Π_{0}) = aceita).

Das duas equações acima temos que

ω(G_{x}) = 2^{r̂(n)} max_{Π} ℙ_{τ}(V (x, τ, Π) = aceita).

Mas, pela definição de sistemas PCP,

max_{Π} ℙ_{τ} (V (x, τ, Π) = aceita) \{ \begin{matrix}= 1 & se x ∈ L \\ < 1/4 & se x ∉ L. \end{matrix}

Portanto, mostramos que G_{x} e f(n) = 2^{r̂(n)} são de acordo com as equações (30) e (31). □

Seja PCP(r(n), q(n), ε) a classe de linguagens definida da mesma forma que PCP(r(n), q(n)), exceto que o limite superior 1/4 para a probabilidade do verificador ser ludibriado é trocado por ε. Como já observado (veja Capítulo III),

PCP(r(n), q(n), ε) = PCP(r(n), q(n))

se ε é uma constante. A razão disso é que podemos repetir em paralelo um número conveniente (constante) de vezes o processo de verificação e diminuir arbitrariamente a probabilidade de erro.

Portanto, podemos reescrever a prova do Teorema 69 com ε no lugar de 1/4, obtendo o seguinte resultado.

Teorema 70. Para todo ε > 0 o Problema Clique Máximo não pode ser aproximado em tempo polinomial com grau de aproximação menor que 1 + ε, a menos que P = NP.

Pensando da mesma forma, poderíamos tentar provar o Teorema 68. Repetindo o esquema acima, teríamos que repetir o processo de verificação k vezes, com k satisfazendo (1/4)^{k} ≤ n^{−ε}. Isso implica que k = Ω(ε log n) e assim teríamos que usar Θ(log^{2} n) bits aleatórios ao invés de O(log n). Ademais, agora Θ(log n) consultas seriam necessárias ao invés de O(1), mostrando que NP ⊆ PCP(log^{2} n, log n, n^{−ε}). Com isso, o número de vértices de G_{x} seria

|V (G_{x})| ≤ 2^{r̂(n)}2^{q̂(n)} = 2^{O(log^{2} n+log n)},

o que não é satisfatório pois esse número não é limitado por nenhum polinômio em n. Porém, veremos na próxima seção que usando outros métodos bastante poderosos poderemos mostrar que

NP ⊆ PCP(log n, log n, n^{−ε}),

o que prova o Teorema 68.

3.3. NP ⊆ PCP(log n, log n, n^{−ε}). A dificuldade em se usar o resultado PCP(log n, 1) = NP para provar a impossiblidade de um grau de aproximação de n^{ε} para o Problema Clique Máximo decorre do fato de termos que recorrer a O(log^{2} n) bits aleatórios. Porém, vamos mostrar como O(log n) bits aleatórios podem gerar O(log^{2} n) bits pseudo-aleatórios, que podem ser usados em um procedimento de verificação (log n, 1)-restrito.

A idéia é a seguinte. Para uma constante d, vamos escolher adequadamente um grafo d-regular G com 2^{r} vértices rotulados com todos os número binários de 0 a 2^{r} − 1. Vamos agora descrever um passeio aleatório em G. (Para detalhes sobre passeios aleatórios veja Apêndice B.) Inicialmente uma partícula é colocada num vértice de G escolhido uniformemente ao acaso. No passeio aleatório o próximo vértice a ser visitado pela partícula é escolhido uniformemente ao acaso dentre os d adjacentes ao vértice atual. Vamos escolher, a cada c vértices visitados, o rótulo do vértice que acaba de ser visitado como uma seqüência de r bits pseudo-aleatórios, onde c é uma constante adequada. Visitando-se um total de ct vértices, obtemos os tr bits pseudo-aleatórios que serão usados. Note que o custo de se visitar ct vértices desta forma é de

r + ⌈log_{2} d⌉(ct − 1) = r + O(t)

bits (genuinamente) aleatórios. O próximo lema nos dá a justificativa desse método.

No lema abaixo, G_{d,ρ} é a família de grafos d-regulares com a seguinte propriedade. Se G é membro de G_{d,ρ} e A é a sua matriz de adjacência multiplicada por 1/d, então todos menos o maior dos auto-valores de A são positivos e menores do que 1 − ρ.

Lema 71. Seja G = (V, E) ∈ G_{d,ρ}. Considere um passeio aleatório P em G com início em um vértice escolhido uniformemente ao acaso. Então, existe um inteiro c = c_{ρ} tal que, para qualquer subconjunto C de V com |C| ≤ |V |/4, a probabilidade do trecho inicial de P de comprimento kc visitar a cada c passos algum vértice de C é de no máximo (3/4)^{k}.

Prova. Seja G = (V, E) de acordo com o enunciado do teorema, com V = {1, 2, …, n}. Vamos usar o fato bem conhecido (veja, por exemplo, Lovász [Lov93, Exercício 11.4]) que o maior auto-valor de uma matriz de adjacência de um grafo d-regular é d. Segue daí que o maior auto-valor de A, a matriz de adjacência de G multiplicada por 1/d, é 1. Sejam 1 = λ_{0} > λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{m} > 0 os auto-valores de A. Como λ_{1} ≤ 1 − ρ, existe um inteiro c tal que λ_{1}^{c} ≤ 1/4. Seja p^{(t)} = (p_{1}^{(t)}, p_{2}^{(t)}, …, p_{n}^{(t)}) ∈ ℝ^{n} o vetor de probabilidades com p_{i}^{(t)} sendo a probabilidade do vértice i estar sendo visitado no tempo t. Como o primeiro vértice de G é escolhido ao acaso, o vetor p^{(0)} é o vetor cujas entradas são todas 1/n.

É fácil de se verificar que Ap^{(0)} = p^{(1)}, e em geral A^{t}p^{(0)} = p^{(t)}. Note simplesmente que A é a matriz de transição da cadeia de Markov definida pelo passeio aleatório.

Seja C um subconjunto qualquer de V com |C| ≤ n/4. Seja N a matriz com zero em todas as entradas, exceto na diagonal, onde N_{ii} = 1 se e só se i ∈ C. Então o vetor NA^{c}p^{(0)} nos dá, para cada vértice v ∈ C, a probabilidade do passeio estar visitando v após c passos. O vetor NA^{c}(NA^{c}p^{(0)}) nos dá a probabilidade do passeio visitar vértices de C no passo c e no passo 2c. Em geral, (NA^{c})^{k}p^{(0)} nos dá a probabilidade de um passeio aleatório de comprimento kc atingir a cada c passos um vértice de C.

Vamos denotar a seguir a norma ℓ_{1} de um vetor v por |v| (i.e., |v| = ∑_{1}^{n} |v_{i}|) e a norma ℓ_{2} por ∥v∥ (i.e., ∥v∥ = \sqrt{∑_{1}^{n} v_{i}^{2}}).

Claramente |(NA^{c})^{k}p^{(0)}| é a probabilidade do passeio de comprimento kc atingir a cada c passos um vértice de C. Para limitar essa probabilidade vamos inicialmente limitar |NA^{c}p|, onde p é um vetor qualquer. Para tanto, é mais fácil trabalharmos com a norma ℓ_{2}. Escreva p como a soma de dois vetores ortogonais v e w, onde v é múltiplo de p^{(0)}. Note que p^{(0)} é um auto-vetor associado ao auto-valor λ_{0} = 1 e w é combinação linear de auto-vetores associados aos auto-valores λ_{1}, λ_{2}, …, λ_{m}. Assim,

∥NA^{c}v∥ = ∥Nv∥ = \sqrt{∑_{N_{ii}=1} v_{i}^{2}} ≤ \sqrt{\frac{1}{4} ∑_{i=1}^{n} v_{i}^{2}} = \frac{1}{2}∥v∥  (32)

e

∥NA^{c}w∥ ≤ ∥A^{c}w∥ ≤ λ_{1}^{c}∥w∥ ≤ \frac{1}{4}∥w∥.  (33)

Usando a desigualdade triangular obtemos

∥NA^{c}p∥ = ∥NA^{c}(v + w)∥ ≤ ∥NA^{c}v∥ + ∥NA^{c}w∥
≤ \frac{1}{2}∥v∥ + \frac{1}{4}∥w∥ ≤ \frac{1}{2}∥p∥ + \frac{1}{4}∥p∥ ≤ \frac{3}{4}∥p∥.

Fazendo uso k vezes da desigualdade acima, temos

∥(NA^{c})^{k}p^{(0)}∥ ≤ (\frac{3}{4})^{k} ∥p^{(0)}∥ = (\frac{3}{4})^{k} \frac{1}{\sqrt{n}}.

Agora, lembrando que para qualquer vetor v ∈ ℝ^{n} temos |v| ≤ \sqrt{n}∥v∥, obtemos

|(NA^{c})^{k}p^{(0)}| ≤ \sqrt{n}∥(NA^{c})^{k}p^{(0)}∥ ≤ \sqrt{n} (\frac{3}{4})^{k} \frac{1}{\sqrt{n}} = (\frac{3}{4})^{k} ,

como queríamos demonstrar. □

A prova da existência e construtibilidade em tempo polinomial de infinitos membros da família G_{d,ρ} é tratado no teorema abaixo.

Teorema 72. Existem constantes α, ρ > 0 tais que se n é uma potência de 2 suficientemente grande, então existe um grafo G = (V, E) com n vértices com as seguintes propriedades:

(1) o grau de cada vértice é 7;

(2) o segundo auto-valor λ_{1} de A(G) é menor que 1 − ρ;

(3) dado n, o grafo G pode ser construído em tempo polinomial em n por uma máquina de Turing.

Veremos mais adiante que o fato de termos G em G_{d,ρ} com d = O(1) no teorema acima é importante. Esses grafos são conhecidos como grafos expansores esparsos. Informalmente, um grafo é um expansor se a vizinhança de qualquer subconjunto de seus vértices é relativamente grande. O ‘fator de expansão’ de um grafo G é intimamente ligado ao segundo auto-valor de G. Para detalhes veja o Capítulo 9 de Alon e Spencer [AS92a]. O problema da construção de grafos expansores com grau fixo aparece antes da descoberta de sua utilização como auxiliares na geração de bits pseudo-aleatórios. Embora a existência de tais grafos pode ser facilmente provada probabilisticamente, a construção explícita e eficiente de tais grafos é muito mais difícil. Para um breve apanhado do desenvolvimento de técnicas para a construção de expansores veja Seção 5.

Usando o Lema 71 e o Teorema 72, podemos provar agora o seguinte.

Teorema 73. NP ⊆ PCP(log n, log n, n^{−ε}).

Prova. Seja L uma linguagem em NP e ε > 0 um número real fixo. Seja V um verificador (log n, 1)-restrito para L. Para provar o teorema vamos, a partir de V, construir um verificador (log n, log n)-restrito V_{ε}. Seja r̂(n) = O(log n) o número de bits aleatórios usados por V. Seja x uma palavra cuja pertinência em L deseja-se decidir. Inicialmente, o verificador V_{ε} constrói um grafo G ∈ G_{d,ρ} (d = 7) com 2^{r̂(|x|)} vértices, de acordo com Teorema 72. Seja c um inteiro satisfazendo (1−ρ)^{c} ≤ 1/4. Seja k = ⌈ε log_{4/3} n⌉.

Usando O(log n) bits aleatórios, o verificador V_{ε} faz um passeio aleatório em G de comprimento ck, coletando a cada c passos os rótulos dos vértices visitados. Note que cada passo do passeio aleatório usa somente O(1) bits aleatórios, pois o grafo tem grau O(1). Esses rótulos são usados como bits aleatórios para V_{ε} repetir k vezes o processo de verificação de V. Se alguma vez V rejeita, então V_{ε} rejeita. Caso contrário, V_{ε} aceita.

A probabilidade de V dar uma resposta errada (ou seja V aceita e x ∉ L) é limitada por 1/4. Ou seja, no máximo 1/4 dos rótulos dos vértices de G podem fazer V fornecer uma resposta incorreta. Seja C o conjunto dos vértices de G cujos rótulos correspondem a respostas erradas de V. Usando então o Lema 71, a probabilidade dos k vértices visitados estarem todos em C, ou seja, a probabilidade de todas as k simulações de V devolverem aceita erroneamente, é, no máximo,

(\frac{3}{4})^{k} ≤ (\frac{3}{4})^{ε log_{4/3} n} = n^{−ε},

como queríamos. □

4. Demonstrações dos Teoremas 44 e 45

Os Teoremas 44 e 45, já enunciados, serão provados a seguir.

Teorema 44. O Problema Mochila Máxima está em EAP.

Prova. Precisamos mostrar que para qualquer ε > 0 existe um algoritmo polinomial com grau de aproximação no máximo 1 + ε.

Lembremos que uma instância x do problema consiste de um conjunto U = {u_{1}, u_{2}, …, u_{n}}, duas funções t, v: U → ℤ e um inteiro CAP. Nosso objetivo é obter um subconjunto U′ ⊆ U que maximize

m(x, U′) = ∑_{u∈U′} v(u), sujeito a ∑_{u∈U′} t(u) ≤ CAP .

Definimos a densidade de um u ∈ U como d(u) = v(u)/t(u).

Vamos descrever um procedimento que obtém uma solução aproximada do problema. Fixe um inteiro k ≥ 1. Considere todos os subconjuntos de U com no máximo k elementos. Para cada um desses subconjuntos A, verifique se ∑_{u∈A} t(u) ≤ CAP. Se esse for o caso, tente incluir em A mais elementos de U. Os elementos são considerados para inclusão por ordem decrescente de densidade e colocados em A se e somente se a capacidade CAP da mochila não é violada com a inclusão. Chame o conjunto assim definido de U′. A solução aproximada é a que maximiza m(x, U′) sobre todas as possíveis escolhas de A.

Seja Û uma solução ótima para o problema de maximização. Seja OTIM = m(x, Û). Se |Û| ≤ k então o subconjunto Û é explicitamente considerado pelo procedimento e neste caso a solucão aproximada é igual à solução ótima. Vamos assim supor que |Û| > k.

Seja B ⊆ U o conjunto dos k elementos de Û de maior valor. Seja \overline{U} ⊆ U o candidato à solução obtido pelo procedimento descrito acima quando o conjunto B é considerado. Vamos mostrar que

\frac{OTIM}{m(x, \overline{U})} ≤ 1 + 1/k.

Sejam u_{i_{1}}, u_{i_{2}}, …, u_{i_{r}} todos os elementos de Û \ \overline{U} ordenados por ordem decrescente de densidade, ou seja, d(u_{i_{1}}) ≥ d(u_{i_{2}}) ≥ ⋯ ≥ d(u_{i_{r}}). Se r = 0 então \overline{U} é uma solução ótima. Vamos supor então que r ≥ 1. O elemento u_{i_{1}} não é um dos k elementos de maior valor em Û, e portanto

v(u_{i_{1}}) ≤ OTIM /(k + 1).  (34)

Seja T = \overline{U} ∩ Û. Sejam u_{j_{1}}, u_{j_{2}}, …, u_{j_{s}} os elementos de \overline{U} \ Û com densidades maiores ou iguais a d(u_{i_{1}}) ordenados por ordem decrescente de densidades. Ou seja,

d(u_{j_{1}}) ≥ d(u_{j_{2}}) ≥ ⋯ ≥ d(u_{j_{s}}) ≥ d(u_{i_{1}}).

Não pode ser o caso que s = 0, pois, por construção, a razão que levou u_{i_{1}} a não ser colocado em \overline{U} é que essa inclusão violaria a capacidade da mochila. Como a inclusão é feita por ordem decrescente de densidade, algum elemento fora de Û, de densidade maior que d(u_{i_{1}}), já teria que estar em \overline{U} quando u_{i_{1}} foi considerado pelo procedimento. Portanto,

∑_{u∈T} t(u) + ∑_{p=1}^{s} t(u_{j_{p}}) + t(u_{i_{1}}) > CAP .

Por outro lado, temos que

∑_{u∈T} t(u) + ∑_{p=1}^{r} t(u_{i_{p}}) ≤ CAP,

pois Û = T ∪ ⋃_{p=1}^{r}{u_{i_{p}}}. Segue das duas equações acima que

∑_{p=1}^{s} t(u_{j_{p}}) + t(u_{i_{1}}) > ∑_{p=1}^{r} t(u_{i_{p}}),

implicando que

∑_{p=1}^{s} t(u_{j_{p}}) > ∑_{p=2}^{r} t(u_{i_{p}}).

Como d(u_{j_{s}}) ≥ d(u_{i_{1}}) ≥ d(u_{i_{p}}), para todo 1 ≤ p ≤ r, temos que v(u_{i_{p}}) ≤ d(u_{j_{s}})t(u_{i_{p}}). Desse fato e da equação acima, segue que

∑_{p=2}^{r} v(u_{i_{p}}) ≤ d(u_{j_{s}}) ∑_{p=2}^{r} t(u_{i_{p}}) ≤ d(u_{j_{s}}) ∑_{p=1}^{s} t(u_{j_{p}}) ≤ ∑_{p=1}^{s} v(u_{j_{p}}).

Portanto,

OTIM = ∑_{u∈T} v(u) + v(u_{i_{1}}) + ∑_{p=2}^{r} v(u_{i_{p}})

≤ ∑_{u∈T} v(u) + v(u_{i_{1}}) + ∑_{p=1}^{s} v(u_{j_{p}})
≤ ∑_{u∈\overline{U}} v(u) + v(u_{i_{1}}) = m(x, \overline{U}) + v(u_{i_{1}}).

Usando (34) obtemos,

OTIM ≤ m(x, \overline{U}) + v(u_{i_{1}}) ≤ m(x, \overline{U}) + OTIM /(k + 1),

ou

\frac{OTIM}{m(x, \overline{U})} ≤ 1 + 1/k.

Escolhendo k = ⌈1/ε⌉ obtemos a aproximação desejada, de acordo com a Definição 43.

Só nos falta mostrar que o procedimento que obtém a aproximação pode ser executado em tempo polinomial. Observe que o número dos subconjuntos A ⊆ U com no máximo k elementos não excede n^{k}. A construção de U′ a partir de A pode ser feita em tempo O(nB), onde B é o número de bits do maior número que aparece na instância do problema, dentre os tamanhos, valores e a capacidade CAP. Podemos gerar sistematicamente todos os subconjuntos com no máximo k elementos através de um processo que nos fornece o próximo subconjunto a partir do anterior. Cada passo dessa construção pode ser feito em tempo O(k log n). Portanto, o algoritmo todo pode ser executado em tempo O(n^{k} × nB × k log n) ou O(Bn^{k+1} log n) considerando-se k constante. Em outros termos, uma vez fixado ε, o algoritmo com grau de aproximação 1 + ε roda em tempo O(Bn^{⌈1/ε⌉+1} log n). □

Teorema 45. O Problema Max-3sat está em APX.

Prova. Lembre-se de que uma instância do Problema Max-3sat é uma coleção de cláusulas C = {c_{1}, c_{2}, …, c_{m}} sob um conjunto finito U de variáveis, com |c_{i}| = 3 para 1 ≤ i ≤ m. Seja U = {u_{1}, u_{2}, …, u_{n}} o conjunto de variáveis.

Para provar que o problema está em APX, basta mostrar um ε > 0 e um algoritmo A que aproxime o problema com grau de aproximação r ≤ 1 + ε. Vamos mostrar um algoritmo com grau de aproximação no máximo 2.

O algoritmo é bastante simples. Inicialmente considere o conjunto de cláusulas C_{1} ⊆ C nas quais a variável u_{1} aparece. Atribua o valor V ou F a u_{1} de forma a maximizar o número de cláusulas satisfeitas em C_{1}. Pelo menos metade dessas cláusulas podem ser satisfeitas.

Num passo i defina o conjunto de cláusulas

C_{i} ⊆ C \ (C_{1} ∪ C_{2} ∪ ⋯ ∪ C_{i−1})

nas quais a variável u_{i} aparece. Atribua o valor V ou F a u_{i} de forma a maximizar o número de cláusulas satisfeitas em C_{i}. Pelo menos metade dessas cláusulas podem ser satisfeitas.

Podemos facilmente constatar que a atribuição acima definida satisfaz pelo menos metade de todas as cláusulas de U, e, portanto, o valor ótimo para o problema é no máximo 2 vezes maior que o valor obtido pela atribuição. □

5. Notas Bibliográficas

Os pilares para o estudo das classes de complexidade em computação foram lançados no início dos anos 70 por Stephen Cook [Coo71], com as noções das classes P e NP e a prova de que o Problema Satisfatibilidade é NP-completo, que ficou conhecida como o Teorema de Cook. A redução de Karp aparece em [Kar91]. Enquanto isso, atrás da cortina de ferro, muito antes da proliferação do uso da Internet e do correio eletrônico, L. Levin [Lev72] provou independentemente uma variante do Teorema de Cook e define um outro tipo de redução, que passou a ser conhecida como redução de Levin. Para uma coleção detalhada de problemas NP-completos o leitor poderá consultar Garey e Johnson [GJ79], onde encontrará uma excelente introdução ao assunto.

O Teorema 64 que mostra que o Problema Mochila Máxima está em EAP é de Sahni [Sah75]. Dentre os primeiros resultados mostrando a impossibilidade de certas aproximações estão os Teoremas 64 e 65 de Garey e Johnson [GJ76] e Sahni e Gonzales [SG76] respectivamente.

Conforme já mencionado, para as definições de classes de problemas de aproximação estamos seguindo as definições de Ausiello et al. [ACP94], posteriores ao trabalho pioneiro de Papadimitriou e Yannakakis [PY88].

A conexão entre provas interativas e a impossibilidade de se aproximar cliques em grafos foi estabelecida por Feige, Goldwasser, Lovász, Safra e M. Szegedy [FGL^{+}91]. O primeiro trabalho estabelecendo essa conexão, que de certa forma passou desapercebido, é de Condon [Con93].

As técnicas usadas para mostrar como O(log n) bits aleatórios podem gerar O(log^{2} n) bits pseudo-aleatórios são de Cohen e Wigderson [CW89] e Impagliazzo e Zuckerman [IZ89], inspirados em Ajtai, Komlós e Szemerédi [AKS87].

O problema da construção de grafos expansores com grau fixo aparece antes da utilização destes como auxiliares na geração de bits pseudo-aleatórios. Embora a existência de tais grafos pode ser facilmente provada probabilisticamente, a construção explícita e eficiente de tais grafos é muito mais difícil. A primeira construção foi dada por Margulis [Mar75], usando a teoria da representação de grupos de Lie. Uma versão melhorada é obtida em Gabber e Galil [GG81] e se baseia em análise de Fourier comutativa. O Teorema 72 é mencionado em [AKS87] e é baseado na construção de [GG81]. Posteriormente, a conexão entre auto-valores e propriedades expansivas de grafos, que aparece no teorema acima, é estabelecida em Alon e Milman [AM85], e Alon [Alo86], servindo também como base para melhores estimativas de λ_{1}. Isso possibilitou que, em trabalhos similares, Margulis [Mar88] e Lubotzky, Phillips e Sarnak [LPS88] melhorassem bastante as propriedades expansivas obtidas. Para a construção de grafos com λ_{1} pequeno foi usada, entre outros, a teoria dos números, incluindo resultados sobre uma conjectura de Ramanujan sobre o número de representações de inteiros por certas formas quadráticas.

APÊNDICE A LISTA DE PROBLEMAS

Neste apêndice estão listadas as definições dos vários problemas mencionados no decorrer do trabalho. O estilo da apresentação é o usado por Garey e Johnson [GJ79] (problemas de decisão) e por Crescenzi e Kann [CK94] (problemas de otimização). Estas duas referências trazem listagens e classificações quanto à complexidade de centenas de problemas.

1. Problemas de Decisão

Árvore de Steiner Instância: Um grafo G, um subconjunto S de seus vértices e um inteiro positivo k. Problema: Existe um subgrafo conexo de G contendo todos os vértices de S e tendo menos do que k arestas?

Passeio do Caixeiro Viajante Instância: Um conjunto finito C = {c_{1}, c_{2}, …, c_{m}} de “cidades,” uma “distância” d(c_{i}, c_{j}) ∈ ℕ para cada par de cidades c_{i}, c_{j} ∈ C, e um inteiro positivo L Problema: Existe um passeio de Caixeiro Viajante, i.e., um passeio que visite todas as cidades e retorne à cidade de origem, de comprimento no máximo L ?

Circuito Hamiltoniano Instância: Um grafo G.

Problema: Existe um circuito hamiltoniano em G, i.e., um circuito que passa exatamente uma vez por cada vértice de G?

Clique Instância: Um grafo G = (V, E) e um inteiro k. Problema: O grafo G tem um clique de tamanho k, i.e., existe C ⊆ V com |C| = k tal que quaisquer dois vértices distintos em C são adjacentes?

Coloração Instância: Um grafo G = (V, E) e um inteiro k. Problema: O grafo G tem uma k-coloração própria, i.e., existe uma função f: V → {1, 2, …, k} tal que f(v) ≠ f(w) sempre que vw ∈ E?

Corte em Grafos Instância: Um grafo G = (V, E) e um inteiro positivo k. Problema: Existe uma partição de V em V_{1} e V_{2} tais que o número de arestas ligando vértices de V_{1} a vértices de V_{2} é pelo menos k?

QBF Instância: Uma fórmula booleana quantificada

F = (Q_{1}x_{1})(Q_{2}x_{2}) … (Q_{n}x_{n})B(x_{1}, x_{2}, …, x_{n}),

onde B é uma fórmula booleana sem quantificadores e cada Q_{i} é ou ∃ ou ∀. Problema: É F verdadeira?

Grafo Não-Isomorfismo Instância: Dois grafos G_{1} e G_{2}. Problema: G_{1} e G_{2} são não-isomorfos? (Dizemos que dois grafos H_{1} = (V, E_{1}) e H_{2} = (V, E_{2}) são isomorfos se existe uma função bijetora f : V → V tal que uv ∈ E_{1} se e somente se f(u)f(v) ∈ E_{2}.)

Mochila Instância: Um conjunto finito U, para cada u ∈ U um tamanho inteiro t(u) e um valor inteiro v(u), uma capacidade inteira CAP e um inteiro c. Problema: Existe um subconjunto U′ ⊆ U tal que ∑_{u∈U′} t(u) ≤ CAP (a soma dos tamanhos dos elementos em U′ é no máximo a capacidade da mochila) e ∑_{u∈U′} v(u) ≥ c (o valor total colocado na mochila é pelo menos c)?

Primalidade Instância: Um número inteiro positivo n. Problema: É n um número primo?

2sat Instância: Uma coleção de cláusulas C = {c_{1}, c_{2}, …, c_{m}} sobre um conjunto finito U de variáveis, com |c_{i}| = 2 para 1 ≤ i ≤ m e um inteiro positivo k. Problema: Existe uma atribuição às variaveis de U que satisfaça pelo menos k cláusulas?

3sat Instância: Uma coleção de cláusulas C = {c_{1}, c_{2}, …, c_{m}} sobre um conjunto finito U de variáveis, com |c_{i}| = 3 para 1 ≤ i ≤ m. Problema: Existe uma atribuição para U que satisfaça a todas as cláusulas de C?

Satisfatibilidade Instância: Uma coleção de cláusulas C = {c_{1}, c_{2}, …, c_{m}} sobre um conjunto finito U de variáveis. Problema: Existe uma atribuição para U que satisfaça a todas as cláusulas de C?

2. Problemas de Otimização

Árvore Mínima de Steiner Instância: Um grafo G e um subconjunto S de seus vértices. Solução: Uma subgrafo conexo T contendo todos os vértices de S. Função objetivo: Número de arestas em T.

Passeio do Caixeiro Viajante Mínimo Instância: Um conjunto finito C = {c_{1}, c_{2}, …, c_{m}} de “cidades,” uma “distância” d(c_{i}, c_{j}) ∈ ℕ para cada par de cidades c_{i}, c_{j} ∈ C, e um inteiro positivo L Solução: Um passeio de Caixeiro Viajante, i.e., um passeio que visite todas as cidades em C e retorne à cidade de origem. Função objetivo: Comprimento total do passeio.

Coloração Mínima Instância: Um grafo G = (V, E). Solução: Uma k-coloração própria de G, i.e., uma função

f : V → {1, 2, …, k}

tal que f(v) ≠ f(w) sempre que vw ∈ E. Função objetivo: O inteiro k.

k-coloração Máxima Instância: Um grafo G. Solução: Um subgrafo H de G que tenha uma k-coloração própria. (Aqui, k ≥ 2 é uma constante, não fazendo parte da entrada.) Função objetivo: O número de arestas de H.

Clique Máximo Instância: Um grafo G = (V, E). Solução: Um clique de G, i.e., um subconjunto C ⊆ V tal que quaisquer dois vértices distintos em C são adjacentes. Função objetivo: Cardinalidade de C.

Corte Máximo Instância: Um grafo G = (V, E). Solução: Subconjuntos X do conjunto de vértices de G. Função objetivo: Número de arestas entre X e V \ X.

Max-2sat Instância: Uma coleção de cláusulas C = {c_{1}, c_{2}, …, c_{m}} sobre um conjunto finito U de variáveis, com |c_{i}| = 2 para 1 ≤ i ≤ m. Solução: Uma atribuição A às variáveis de U. Função objetivo: O número de cláusulas satisfeitas por A.

Max-3sat Instância: Uma coleção de cláusulas C = {c_{1}, c_{2}, …, c_{m}} sobre um conjunto finito U de variáveis, com |c_{i}| = 3 para 1 ≤ i ≤ m. Solução: Uma atribuição A às variáveis de U. Função objetivo: O número de cláusulas satisfeitas por A.

Max-sat Instância: Uma coleção de cláusulas C = {c_{1}, c_{2}, …, c_{m}} sobre um conjunto finito U de variáveis. Solução: Uma atribuição A às variáveis de U. Função objetivo: O número de cláusulas satisfeitas por A.

Mochila Máxima Instância: Um conjunto finito U, para cada u ∈ U um tamanho inteiro t(u) e um valor inteiro v(u), e uma capacidade inteira CAP. Solução: Um subconjunto U′ ⊆ U tal que ∑_{u∈U′} t(u) ≤ CAP (a soma dos tamanhos dos elementos em U′ é no máximo a capacidade da mochila). Função objetivo: O valor ∑_{u∈U′} v(u) (a soma dos valores dos elementos colocados na mochila).

Super String Mínimo Instância: Um conjunto S de palavras. Solução: Uma palavra w contendo cada palavra de S como segmento, i.e., para qualquer s ∈ S, existem w_{1}, w_{2}, tais que w = w_{1}sw_{2} Função objetivo: Comprimento de w.

94 A. LISTA DE PROBLEMAS

APÊNDICE B DEFINIÇÕES

A intenção deste apêndice é relembrar rapidamente o leitor de algumas definições básicas que são usadas nestas notas. Mais detalhes podem ser vistos em livros clássicos de teoria dos grafos e combinatória como os livros [BM79, Bol79] e [Lov93]. O restante das definições são dadas durante o desenvolvimento dos tópicos. Para tais definições, consulte o Índice Remissivo.

1. Notação Assintótica

Seja f e g duas funções f, g : ℕ → ℝ. Escrevemos que

f = O(g)

(f é da ordem de g) se existe uma constante c > 0 tal que para todo n suficientemente grande temos que |f(n)| ≤ c|g(n)|.

Escrevemos que

f = Ω(g)

se g = O(f).

Escrevemos que

g = Θ(f)

se f = O(g) e g = O(f).

2. Terminologia da Teoria dos Grafos

Um grafo G consiste de um conjunto finito não-vazio V (G) de vértices e um conjunto finito E(G) de pares não-ordenados de vértices, chamados arestas. Uma aresta {x, y} de um grafo G é denotado, por comodidade, tanto por xy como por yx. Os extremos de uma aresta são os vértices contidos nela. Escrevemos G = (V (G), E(G)). Dizemos que uma aresta liga o par de vértices que são seus extremos. Dois vértices são adjacentes se são ligados por alguma aresta do grafo. Se v é um extremo de uma aresta f, dizemos que f e v são incidentes ou adjacentes.

O número de arestas incidentes a um vértice v é o grau de v; denotamos esta quantidade por grau(v). Um grafo G é k-regular se todos os seus vértices têm grau k.

Dado um grafo G, uma função φ: V (G) → K é muitas vezes dita ser uma coloração dos vértices de G pelas cores em K. Se |K| = k, dizemos que φ é uma k-coloração. A coloração φ é própria se vértices adjacentes em G recebem cores distintas, i.e., se para toda aresta xy de G temos φ(x) ≠ φ(y). O número cromático χ(G) de um grafo G é o menor inteiro k para o qual existe uma k-coloração própria de G.

Um clique em um grafo G é um subgrafo completo de G, i.e., um subgrafo cujos vértices são todos dois-a-dois adjacentes. Um clique de um grafo G é máximo se não há em G um clique com uma quantidade maior de vértices. O número de vértices em um clique máximo de G é denotado por ω(G).

Um passeio em um grafo é uma seqüência de vértices v_{0}, v_{1}, …, v_{k} tal que v_{i−1} e v_{i} são adjacentes para todo 1 ≤ i ≤ k. Um caminho é um passeio sem vértice repetidos. Um circuito é um passeio fechado, i.e., com v_{0} = v_{k}, e sem vértices repetidos (a menos de v_{0} = v_{k}). Um circuito hamiltoniano é um circuito que contém (‘passa’) por todos os vértices do grafo. Um grafo é hamiltoniano se ele contém um circuito hamiltoniano.

A matriz de adjacência de um grafo G com vértices v_{1}, v_{2}, …, v_{n} é a matriz

A_{G} = (a_{ij})_{i,j=1}^{n} ,

onde a_{ij} é o número de arestas ligando v_{i} a v_{j}. Note que esta matriz é simétrica.

Seja G = (V, E) um grafo com V = {1, 2, …, n}. Um passeio aleatório em G é uma seqüência de vértices (X_{t})_{0}^{∞} visitados por uma partícula que começa num vértice especificado e visita outros vértices de acordo com a seguinte regra de transição: se a partícula está num vértice i no tempo t ou, formalmente, X_{t} = i, então no tempo t + 1 ela se move a um vértice adjacente a i escolhido uniformemente ao acaso. Pode ser facilmente verificado que a seqüência (X_{t}) é uma cadeia de Markov com matriz de transição A = (a_{ij})_{i,j=1}^{n} com

a_{ij} = \begin{cases}1/ grau(j) & se i e j são adjacentes em G \\ 0 & caso contrário. \end{cases}

3. Terminologia da Lógica

Seja U = {u_{1}, u_{2}, …, u_{n}} um conjunto de variáveis booleanas. Uma atribuição para U é uma função t: U → {V, F}. Se t(u) = V dizemos que u é ‘verdadeira’ sob a atribuição. Se t(u) = F dizemos que u é ‘falsa.’ Dizemos que u e ū = ¬u são literais sob U. O literal u é verdadeiro sob t se e somente se t(u) = V. O literal ¬u é verdadeiro sob t se e somente se t(u) = F.

Uma cláusula sobre U é um conjunto de literais sobre U. Uma cláusula representa a disjunção daqueles literais e é satisfeita por uma atribuição se e somente pelo menos um de seus membros é verdadeiro sob a atribuição. Uma coleção de cláusulas é satisfatível se existe uma atribuição para U que satisfaça todas as suas cláusulas simultanemante.

Uma fórmula atômica é um literal ou uma das constantes V ou F. Uma fórmula booleana é uma fórmula atômica ou é da forma ¬A, (A∨B) ou (A∧B), onde A e B são fórmulas. Uma fórmula é satisfatível se existe uma atribuição para a qual a fórmula é verdadeira.

Os seguintes fatos elementares são bem conhecidos.

Fato 74. Dada uma fórmula A, existe uma coleção de cláusulas C de tamanho polinomial no comprimento de A tal que A é satisfatível se e somente se C o é.

Fato 75. Dada uma coleção de cláusulas C, existe uma outra coleção de cláusulas D, com no máximo três literais por cláusula e de

98 B. DEFINIÇÕES

tamanho polinomial no tamanho de C, tal que C é satisfatível se e somente se D o é.

REFERÊNCIAS

[ACP94] G. Ausiello, P. Crescenzi, and M. Protasi, Approximate solution of NP optimization problems, Tech. Report SI/RR 94/03, Università di Roma “La Sapienza”, 1994.

[AKS87] M. Ajtai, J. Komlós, and E. Szemerédi, Deterministic simulation in LOGSP ACE, Proc. 19th Ann. ACM Symp. on Theory of Computing, 1987, pp. 132–140.

[ALM^{+}92a] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, On the intractability of approximation problems (early draft), Manuscrito, 1992.

[ALM^{+}92b] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems, Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science, 1992, pp. 14–23.

[Alo86] N. Alon, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Combinatorica 6 (1986), no. 3, 207–219.

[AM85] N. Alon and V. Milman, λ_{1}, isoperimetric inequalities for graphs, and superconcentrators, Journal of Combinatorial Theory, Series B 38 (1985), 73–88.

[Aro94] S. Arora, Probabilistic Checking of Proofs and Hardness of Approximation Problems, Ph.D. thesis, U. of California at Berkeley, 1994.

[AS92a] N. Alon and J. Spencer, The Probabilistic Method, John Wiley and Sons, Inc., 1992.

[AS92b] S. Arora and S. Safra, Probabilistic checking of proofs, Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science,

1992, pp. 2–13.

[Bab85] L. Babai, Trading group theory for randomness, Proc. 17th Ann. ACM Symp. on Theory of Computing, 1985, pp. 421– 429.

[Bab90] L. Babai, E-mail and the unexpected power of interaction, Proc. 5th IEEE Symp. on Structure in Complexity Theory, 1990, pp. 30–44.

[Bab94] L. Babai, Transparent proofs and limits to approximation, Tech. Report TR-94-07, University of Chicago, 1994, To appear in the Proc. First Europ. Congr. Math., Birkhäuser.

[BFL91] L. Babai, L. Fortnow, and C. Lund, Non-deterministic exponential time has two-prover interactive protocols, Computational Complexity 1 (1991), 3–40.

[BFLS91] L. Babai, L. Fortnow, L.A. Levin, and M. Szegedy, Checking computations in polylogarithmic time, Proc. 23rd Ann. ACM Symp. on Theory of Computing, 1991, pp. 21–31.

[BGLR93] M. Bellare, S. Goldwasser, C. Lund, and A. Russel, Efficient probabilistically checkable proofs and applications to approximation, Proc. 25th Ann. ACM Symp. on Theory of Computing, 1993, pp. 294–304.

[BGLR94] M. Bellare, S. Goldwasser, C. Lund, and A. Russel, Efficient probabilistically checkable proofs and applications to approximation, Proc. 26th Ann. ACM Symp. on Theory of Computing, 1994, Errata, p. 820.

[BK89] M. Blum and S. Kannan, Designing programs that check their work, Proc. 21st Ann. ACM Symp. on Theory of Computing, 1989, pp. 86–97.

[BLR90] M. Blum, M. Luby, and R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Proc. 22nd Ann. ACM Symp. on Theory of Computing, 1990, pp. 73–83.

[BM79] J. Bondy and U. Murty, Graph Theory with Applications, North-Holland, New York, 1979.

[BM88] L. Babai and S. Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes, Journal of Computer and System Sciences 36 (1988), 254–276.

[Bol79] B. Bollobás, Graph Theory—an Introductory Course, Graduate Texts in Mathematics, vol. 63, Springer-Verlag, New York, 1979.

[CK94] P. Crescenzi and V. Kann, A compendium of NP optimization problems, 1994, Versão Preliminar. Disponível por ftp anônimo

de nada.kth.se.

[Con93] A. Condon, The complexity of the max word problem and the power of one-way interactive proof systems, Computational Complexity 3 (1993), 292–305.

[Coo71] S. Cook, The complexity of theorem-proving procedures, Proc. 3rd Ann. ACM Symp. on Theory of Computing, 1971, pp. 151– 158.

[CR73] S.A. Cook and R.A. Reckhow, Time bounded random access machines, Journal of Computer and System Sciences 7 (1973), no. 4, 354–375.

[CW89] A. Cohen and A. Wigderson, Dispersers, deterministic amplification, and weak random sources, Proc. 30th Ann. IEEE Symp. on Foundations of Computer Science, 1989, pp. 14–19.

[Edm65a] J. Edmonds, Minimum partition of a matroid into independent sets, Journal of Research of the National Bureau of Standards (B) 69 (1965), 67–72.

[Edm65b] J. Edmonds, Paths, trees, and flowers, Canadian J. of Mathematics 17 (1965), 449–467.

[FGL^{+}91] U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy, Approximating clique is almost NP-complete, Proc. 32nd Ann. IEEE Symp. on Foundations of Computer Science, 1991, pp. 2– 12.

[FL92] U. Feige and L. Lovász, Two-prover one-round proof systems: their power and their problems, Proc. 24th Ann. ACM Symp. on Theory of Computing, 1992, pp. 733–744.

[GG81] O. Gabber and Z. Galil, Explicit constructions of linear-sized superconcentrators, Journal of Computer and System Sciences 22 (1981), 407–420.

[GJ76] M.R. Garey and D.S. Johnson, The complexity of near-optimal graph coloring, Journal of the ACM 23 (1976), 43–49.

[GJ79] M.R. Garey and D.S. Johnson, Computers and Intractability: a Guide to the Theory of NP-completeness, W. H. Freeman and Company, 1979.

[GMR85] S. Goldwasser, S. Micali, and C. Rackoff, The knowledge complexity of interactive proof-systems, Proc. 17th Ann. ACM Symp. on Theory of Computing, 1985, pp. 291–304.

[Gol94] O. Goldreich, Probabilistic proof systems (a survey), Electronic Colloquium on Computational Complexity, 1994, Report Nr.: TR94–008.

[GS86] S. Goldwasser and M. Sipser, Private coins versus public coins in interactive proof systems, Proc. 18th Ann. ACM Symp. on Theory of Computing, 1986.

[HPS94] S. Hougardy, H.J. Prömel, and A. Steger, Probabilistically checkable proofs and their consequences for approximation algorithms, Discrete Mathematics 136 (1994), 175–223.

[IZ89] R. Impagliazzo and D. Zuckerman, How to recycle random bits, Proc. 30th Ann. IEEE Symp. on Foundations of Computer Science, 1989, pp. 248–253.

[Kar72] R.M. Karp, Reducibility among combinatorial problems, Complexity in Computer Computations (New York) (R.E. Miller and J.W. Thatcher, eds.), Plenum Press, 1972, pp. 85–103.

[Kar91] R. Karp, An introduction to randomized algorithms, Disc. Applied Math. 34 (1991), 165–201.

[Lev72] L. Levin, Problemas universais de busca, Problemy Peredachi

Informatsii 9 (1972), no. 3, 265–266, em russo.

[LFKN92] C. Lund, L. Fortnow, H. Karloff, and N. Nisan, Algebraic methods for interactive proof systems, Journal of the ACM 39 (1992), 859–868.

[Lip91] R. Lipton, New directions in testing, Distributed computing and cryptography, American Mathematical Society, 1991, pp. 191–202.

[Lov93] L. Lovász, Combinatorial Problems and Exercises, 2nd ed., North-Holland, New York, 1993.

[LPS88] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261–277.

[LSS^{+}77] C. Lucchesi, Imre Simon, Istvan Simon, Janos Simon, and T. Kowaltowski, Aspectos Teóricos da Computação, 11^{o} Colóquio Brasileiro de Matemática, Poços de Caldas, 1977.

[Mar75] G.A. Margulis, Explicit construction of concentrators, Problems of Information Transmission 9 (1975), 325–332.

[Mar88] G.A. Margulis, Combinatorial schemes and their application to the design of expanders and concentrators, Problems of Information Transmission 24 (1988), 39–46.

[Mat93] Yuri M. Matiyasevich, Hilbert’s Tenth Problem, MIT Press, Cambridge MA, 1993.

[Pra75] V. Pratt, Every prime has a succint certificate, SIAM Journal on Computing 4 (1975), 214–220.

[PS94] A. Polishchuk and D.A. Spielman, Nearly-linear size holographic proofs, Proc. 26th Ann. ACM Symp. on Theory of Computing, 1994, pp. 194–203.

[PY88] C.H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, Proc. 20th Ann. ACM Symp. on Theory of Computing, 1988, pp. 229–234.

[Sah75] S. Sahni, Approximate algorithms for 0/1 knapsack problem, Journal of the ACM 22 (1975), 115–124.

[SG76] S. Sahni and T. Gonzales, P-complete approximation problems, Journal of the ACM 23 (1976), 555–565.

[Sha92] A. Shamir, IP = P SP ACE, Journal of the ACM 39 (1992), 869–877.

[She92] A. Shen, IP = P SP ACE : simplified proof, Journal of the ACM 39 (1992), 878–880.

[Sim75] Janos Simon, On some central problems in computational complexity, Ph.D. Thesis, Cornell University, Computer Science Tech Report TR 75–224, 1975.

[Sip92] M. Sipser, The history and status of the P versus NP question, Proc. 24th Ann. ACM Symp. on Theory of Computing, 1992, pp. 603–618.

[Sto76] L. Stockmeyer, The polynomial time hierarchy, Theoretical Computer Science 3 (1976), 1–22.

[Sud92] M. Sudan, Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems, Ph.D. thesis, U. of California at Berkeley, 1992.

[Tod89] S. Toda, On the computational power of PP and ⊕P, Proc. 30th Ann. IEEE Symp. on Foundations of Computer Science, 1989, pp. 514–519.

[Tra84] B.A. Trakhtenbrot, A survey of Russian approaches to Perebor (brute-force search) algorithms, Annals of the history of computing 6 (1984), 384–400.

[Tur36] A.M. Turing, On computable numbers with an application to the Entscheidungsproblem, Proc. London Math. Soc. 2 (1936), 230–265, A correction, ibid., 43, pp. 544–546.

[Val79] L. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8 (1979), 189–201.

ÍNDICE REMISSIVO

2sat, 71, 91 3sat, 48, 59, 63, 67, 71, 91 E_{0}, E_{0}^{(q)}, 60, 62, 63 E_{1}, E_{1}^{(q)}, 62, 63 R_{3sat}, 60 S_{1} = S_{1}(r), S_{2} = S_{2}(r), S_{3} =

S_{3}(r), 50

V, 43 V (x, τ, Π), V (x, τ, s, Π), 44, 61 [n] = {1, …, n}, 50 ⟨u, v⟩, 50 aceita, rejeita, 44 AM, 28, 30, 40 APX, 68, 72

completo, 72 difícil, 73

Árvore de Steiner, 71, 89 Árvore Mínima de Steiner, 73,

91

C, C_{i}(x), 49 Circuito Hamiltoniano, 22, 23,

67, 71, 89

Clique, 11, 71, 90 Clique Máximo, 77, 92 Coloração, 71, 90 Coloração Mínima, 74, 92 k-coloração Máxima, 73, 92 Corte em Grafos, 71, 90 Corte Máximo, 73, 92 DTIME, 19 EAP, 68, 72 𝔽_{2}, 49 Grafo Não-Isomorfismo, 30, 90 IP, 7, 28, 30, 37, 40, 41, 49 lfkn, 32, 41 L-redução, 72 MA, 30 Max-2sat, 73, 92 Max-3sat, 73, 75, 86, 92 Max-sat, 73, 92 MAXNP, 74 MAXSNP, 74 Mochila, 71, 90 Mochila Máxima, 84, 93 NP, 5, 18, 21

completo, 48, 70 difícil, 10, 71

NPO, 68

NTIME, 21, 46 #P, 23, 26, 36 P, 6, 10, 18–20 Passeio do Caixeiro Viajante,

71, 89

Passeio do Caixeiro Viajante Mínimo, 74, 91

PCP′(r(n), q(n)), 45 PCP(r(n), q(n)), 44 PCS(r(n), q(n), b(n)), 61 PSPACE, 7, 22, 24, 27, 32, 37, 41,

49

P^{#P}, 36

Φ(y, z), Ψ_{x}(z), 64

Π, Π_{x}, Π_{φ}, 43, 44, 51, 59 Primalidade, 16, 91 ℙ_{ω}, ℙ_{ω∈_{R}Ω}, ℙ_{x,y}, 53 QBF, 37, 90 RAM, 16, 17

e máquina de Turing, 17 SC-Ã(x), SC-B̃(y), SC-C̃(z), 57 Satisfatibilidade, 71, 91 Super String Mínimo, 73, 93 χ(G), 32, 96 coNP, 5, 22, 32

completo, 70 δ-próximo, 53 r̂(n), q̂(n), b̂(n), 44, 61 ∈_{R}, 53 ω(G), 96 poly(n), 45, 46 p-relação, 60, 61 τ, 43 a ∘ a, a ∘ a ∘ a, 51 c = c_{r}, 50 Teste de Consistência, 58 Teste de Linearidade, 55, 58,

59

Teste de Satisfatibilidade, 59

adjacência, 96

matriz de, 96 alfabeto, 18

binário, 18 algoritmo, 19

polinomial, 6, 19 aproximação

grau de, 68 razão de, 68

aresta, 96 aritmetização, 49 atribuição, 49, 97

boa caracterização, 5

cadeia de Markov, 96 candidato à solução, 67 certificado, 4

de pertinência, 43 transparente, 45

circuito hamiltoniano, 4, 96 classe

APX-completo, 72 APX-difícil, 73 DTIME, 19 MAXNP, 74 MAXSNP, 74 NP, 21 NP-completo, 70 NP-difícil, 71 NPO, 68 NTIME, 21 #P, 23 P, 20 PSPACE, 22 coNP, 22, 32 coNP-completo, 70

cláusula, 97 clique, 96

máximo, 11, 77, 96 codificação, 16, 47, 60, 61 de soluções, 59 linear, 51, 62 polinomial, 62 recursiva, 48, 63

codificações

composição de, 48 coloração

k-, 96

própria, 33, 92, 96 complexidade, 19 custo logarítmico, 17

decisão

problema de, 18 demonstração transparente, 45

espaço complexidade de, 16

fita de entrada, 17

de saída, 17 fórmula

atômica, 97 booleana, 97

função aleatória, 57 auto-corretora, 57, 66 em #P, 23 linear homogênea, 53 polinomial, 19

grafo, 96 grafo expansor, 83, 88

contrução de, 88 grau

de aproximação, 68 de um vértice, 96

hamiltoniano

circuito, 4, 22, 23, 96 hierarquia polinomial, 36

Karp

redução de, 70 König

teorema de, 2

limitado polinomialmente, 19 linguagem

definição de, 18 indecidível, 24 recursivamente enumerável, 24

literal, 97

máquina de Turing, 15, 17 e modelo RAM, 17 e programa, 17 polinomial, 19

matriz de adjacência, 96 modelo computacional, 15 não-adaptativo, 44, 61 número cromático, 32, 96

oráculo, 36, 43, 60

palavra, 18 passeio aleatório, 80, 96 polinomial

algoritmo, 19 problema

APX-completo, 73 NP-completo, 71 da parada, 1, 25 de aproximação, 11 de decisão, 18, 89 de enumeração, 23 de maximização, 67 de minimização, 67 de otimização, 67, 91 de pertinência, 18 do banquete pacífico, 6, 36 indecidível, 24 tratável, 19

programa e máquina de Turing, 17 protocolo

Grafo Não-Isomorfismo, 31 lfkn, 32, 36

prova, 60 holográfica, 9 interativa, 7, 27, 36 sistema de, 19 transparente, 9, 45 transparente recursiva, 63 verificável probabilisticamente,

8, 43

razão de aproximação, 68 reconhecimento

de conjuntos, 18 de linguagens, 18

recursiva

classe de linguagem, 24 redução

de Karp, 70, 87 de Levin, 87

restrito verificador (poly(n), 1)-, 48 verificador (r(n), q(n))-, 44 verificador de soluções, 61

segmentada prova, 60 solução, 60

seqüência de bits aleatórios

ios, 43, 83 sistema

com múltiplos provadores, 65 de prova, 19 de prova PCP, 43 de prova interativa, 27

solução, 60 ótima, 67 aproximada, 68 probabilisticamente verificável,

60

tempo

complexidade de, 16 teorema

de Cook, 64, 87 de König, 2

teste

de consistência, 34, 35, 52, 55,

58 de linearidade, 52, 55 de satisfatibilidade, 58

transparente certificado, 43, 45, 48 demonstração, 45 prova, 45, 47 prova quase-linear, 46

Turing, 26

máquina de, 15

verificação

de programas, 66 verificador, 43, 48, 52 de soluções, 60

vértice, 96