Quels problèmes de décision NP ne sont pas auto-réductibles?

8

Nous venons donc d'apprendre sur l'auto-réductibilité en classe. Mon professeur et notre manuel ne s'engageraient pas à dire que tous les problèmes de NP sont auto-réductibles, mais il ne semble pas y avoir d'exemples de problèmes qui ne le soient pas. Je me demandais s'il y avait des exemples, ou si c'était juste une situation où vous ne pouvez pas prouver un négatif facilement. Wikipédia dit seulementIt is conjectured that the integer factorization problem is not self-reducible.

Google a trouvé un résultat , qui semble indiquer que la coloration du graphique plan 4 n'est pas auto-réductible car la coloration LF-k pour un graphique plan se réduit à cette réduction, mais je ne pouvais pas tout à fait suivre la preuve pour le moment.

S'agit-il d'un exemple réel de rejet de l'auto-réductibilité, et en existe-t-il d'autres?

complexity-theory reductions decision-problem np Adam Martin
la source
@DW Non, juste une auto-réductibilité. Lisez l'article.
Yuval Filmus

Réponses:

3

L'article montre en effet que la coloration du graphe planaire quatre n'est pas auto-réductible au sens de Schnorr. Il existe plusieurs autres sens, sous lesquels certains problèmes de P sont auto-réductibles. Voir le document de suivi de Große, Rothe et Wechsung . Je ne connais aucun autre résultat de ce genre. En passant en revue tous les articles citant l'article que vous mentionnez (cela peut être fait en utilisant Google Scholar, par exemple), aucun ne pose de tels problèmes.

Yuval Filmus
la source
Merci! Question rapide cependant, ma compréhension de la partie principale de leur preuve était-elle correcte ou ne l'ai-je pas suivie correctement? Nous n'avons pas fait grand-chose avec les définitions de langage formelles, nous avons été un peu plus abstraits, il est donc difficile d'avoir confiance en ce niveau de détail. (Je vais également attendre un peu pour accepter la réponse, car j'ai une connaissance minimale du sujet et j'aimerais attendre pour voir si d'autres y répondent.)
Adam Martin
Si un problème est auto-réductible au sens de Schnorr et que la version de décision peut être résolue en temps polynomial, alors vous pouvez trouver la première solution lexicographiquement en temps polynomial. Cela repose sur la définition particulière de Schnorr. Dans ce cas, la version de décision est très facile (la réponse est toujours OUI) tandis que la version lex-first est NP-difficile, donc le problème n'est pas auto-réductible sauf si P = NP.
Yuval Filmus
Merci! J'ai l'impression que la seule pierre d'achoppement que j'ai encore, ce sont les différents sens de l'auto-réductibilité. Dois-je poser une autre question, ou s'agit-il d'une distinction assez mineure que je peux demander ici / modifier mon original? Nous avons appris de façon générale qu'un problème est auto-réductible si une solution d'existence de polytime est donnée, vous pouvez créer une solution de recherche de polytime. Existe-t-il ici une distinction technique dont dépend ce résultat?
Adam Martin
1
Jetez un œil à l'article de Große et al., Qui traite de ce point.
Yuval Filmus