Dureza de aproximação sem o teorema do PCP

Uma aplicação importante do teorema do PCP é que ele produz resultados do tipo "dureza de aproximação". Em alguns casos relativamente mais simples, pode-se provar essa dureza sem o PCP. Existe, no entanto, algum caso em que a dureza do resultado da aproximação foi comprovada pela primeira vez usando o teorema do PCP, ou seja, o resultado não era conhecido antes, mas mais tarde foi encontrada uma prova mais direta de que não depende do PCP? Em outras palavras, existe algum caso em que o PCP pareceu necessário primeiro, mas depois poderia ser eliminado?

Um exemplo é este artigo:

Guruswami, V., & Khanna, S. (2004). Sobre a dureza de 4 cores, um gráfico de 3 cores. Jornal SIAM sobre Matemática Discreta , 18 (1): 30-40. ligação

Usando o Teorema PCP, Khanna, Linial e Safra (2000) provaram que é NP-difícil colorir um gráfico de 3 cores usando apenas 4 cores. Mais tarde, Guruswami e Khanna (2004) deram, entre outras coisas agradáveis, uma prova livre de PCP para o mesmo resultado.

Para o problema do máximo de caminhos disjuntos da aresta em gráficos direcionados, o artigo de Ma & Wang (2000) foi baseado no problema da tampa da etiqueta, que por sua vez é baseado no teorema do PCP. Posteriormente, Guruswami et. Encontrou uma redução simples através da dureza do problema de 2 caminhos separados. al. (2003), que também apresentaram dureza aprimorada.

Existem exemplos de contagem aproximada. Contar aproximadamente o número de tarefas satisfatórias de uma relação NP só pode ser mais difícil do que decidir se existe uma tarefa satisfatória; portanto, não é de surpreender que não seja necessário o teorema do PCP para provar a dureza de tais problemas. Ainda assim, o teorema do PCP às vezes fornece um ponto de partida conveniente, por exemplo, para este artigo sobre aproximadamente contar o número de conjuntos independentes em um gráfico esparso: http://www.dcs.ed.ac.uk/home/mrj/papers/ DFJ02.pdf Posteriormente, Sly provou um resultado de dureza para contar aproximadamente conjuntos independentes apenas com base na dureza NP padrão do Max-Cut: http://arxiv.org/pdf/1005.5584v1.pdf

Outra resposta, com um espírito um pouco diferente das respostas anteriores, é este artigo de Uri Feige: Relações entre Complexidade Média de Casos e Complexidade de Aproximação .

Uri mostra que suposições médias de casos podem substituir o teorema do PCP por provar dureza de aproximação de alguns problemas. Observe, no entanto, que não sabemos como provar as suposições de casos médios e temos algumas evidências de que não poderemos prová-las com base nas suposições de dureza NP padrão (consulte os documentos de Feigenbaum-Fortnow, Bogdanov-Trevisan, etc).