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

36

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é?

Andras Farago
la source

Réponses:

35

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.

vb le
la source
11
Seriez-vous prêt à décrire l'article dans votre réponse plutôt que de simplement le pointer avec un lien hypertexte?
Niel de Beaudrap
15

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é.

Chandra Chekuri
la source
Mais la dureté 2-disjointpath nécessite-t-elle le PCP?
Suresh Venkat
3
@SureshVenkat, 2-disjointpaths ne nécessite pas de PCP. Il est le problème de décider s'il y a des chemins disjoints liaison et ( s 2 , t 2 ) dans un graphe orienté G . Il a été démontré que NP-Complete avait été obtenu par Fortune, Hopcroft et Wylie via une réduction complexe du gadget de SAT. (s1,t1)(s2,t2)g
Chandra Chekuri
13

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

Dana Moshkovitz
la source
1
=6
2
cecnc
10

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.).

Dana Moshkovitz
la source