Dureté d'approximation sans le théorème PCP

Une application importante du théorème PCP est qu'il donne des résultats de type "dureté d'approximation". Dans certains cas relativement simples, on peut prouver une telle dureté sans PCP. Existe-t-il toutefois des cas où la dureté du résultat de l'approximation a d'abord été prouvée à l'aide du théorème du PCP, c'est-à-dire que le résultat n'était pas connu auparavant, mais qu'une preuve plus directe a été trouvée plus tard, qui ne dépend pas du PCP? En d'autres termes, existe-t-il un cas où le PCP est apparu nécessaire en premier, mais pourrait ensuite être éliminé?

Un exemple est ce papier:

Guruswami, V. et Khanna, S. (2004). Sur la dureté de 4 couleurs un graphique à 3 couleurs. Journal SIAM sur les mathématiques discrètes , 18 (1): 30-40. lien

L'utilisation du théorème PCP, Khanna, Linial et Safra (2000) a prouvé qu'il était difficile de colorer un graphique à 3 couleurs en utilisant seulement 4 couleurs. Plus tard, Guruswami et Khanna (2004) ont donné, entre autres choses intéressantes, une preuve sans PCP pour le même résultat.

Pour le problème du nombre maximal de chemins disjoints par les arêtes dans les graphes orientés, l'article de Ma & Wang (2000) était basé sur le problème de la couverture des étiquettes, lui-même basé sur le théorème PCP. Par la suite, une simple réduction via la dureté du problème à 2 voies disjointes a été trouvée par Guruswami et. Al. (2003) qui ont également amélioré la dureté.

Il existe des exemples de comptage approximatif. Compter approximativement le nombre d'assignations satisfaisantes d'une relation NP ne peut être plus difficile que de décider si une affectation satisfaisante existe, il n'est donc pas surprenant que le théorème PCP ne soit pas nécessaire pour prouver la dureté de ces problèmes. Néanmoins, le théorème PCP constitue parfois un bon point de départ, par exemple, pour cet article, compter approximativement le nombre d'ensembles indépendants dans un graphe fragmenté: http://www.dcs.ed.ac.uk/home/mrj/papers/ DFJ02.pdf Plus tard, Sly a prouvé un résultat de dureté en comptant approximativement les ensembles indépendants uniquement sur la base de la dureté NP-standard de Max-Cut: http://arxiv.org/pdf/1005.5584v1.pdf

Une autre réponse, qui s'inscrit dans un esprit quelque peu différent des réponses précédentes, est cet article d'Uri Feige: Relations entre complexité moyenne des cas et complexité approximative .

Uri montre que des hypothèses de cas moyennes peuvent remplacer le théorème PCP pour prouver la dureté de l'approximation de certains problèmes. Notez, cependant, que nous ne savons pas comment prouver les hypothèses de cas moyen, et nous avons des preuves que nous ne pourrons pas les prouver sur la base d’hypothèses standard de dureté NP (voir les articles de Feigenbaum-Fortnow, Bogdanov-Trevisan, etc.).