Réductions du livre.

22

C'est dans la ligne des " Algorithmes du livre ". Bien que les réductions soient également des algorithmes, je pensais qu'il était douteux que l'on pense à une réduction en réponse à la question sur les algorithmes du livre. D'où une requête distincte!

Les réductions de toutes sortes sont les bienvenues.

Je vais commencer par la réduction très simple de la couverture des sommets à la découpe multiple sur les étoiles. La réduction se suggère presque une fois que le problème source est identifié (avant quoi je trouverais difficile de croire que le problème serait dur pour les étoiles). Cette réduction implique de construire une étoile avec feuilles et d'associer une paire de bornes à chaque bord du graphique, et il est "facile de voir" que cela fonctionne. Je mettrai à jour cela avec un lien vers une référence, une fois que j'en trouverai un.n

Ceux qui manquent le contexte du livre voudront peut-être regarder la question sur les algorithmes du livre .

Mise à jour: je me rends compte que je n'étais pas tout à fait clair quant à ce qui peut être considéré comme une réduction du livre. Je trouve ce problème un peu délicat, donc j'avoue avoir esquivé à moitié délibérément le problème en glissant une référence à l'autre thread :)

Permettez-moi donc de décrire ce que j'avais à l'esprit, et je suppose que cela va sans dire - YMMV à cet égard. J'ai l'intention de faire une analogie directe avec l'intention originale des épreuves du livre. J'ai vu des réductions qui sont terriblement intelligentes, et je reste bouche bée sur la façon dont cette séquence de pensées a pu arriver à n'importe qui. Bien que de telles réductions me laissent un sentiment de crainte certain, ce ne sont pas les exemples que je cherche à recueillir dans ce contexte.

Ce que je recherche, ce sont des réductions qui sont décrites sans trop de difficulté, et qui sont peut-être légèrement surprenantes, car elles sont faciles à saisir mais pas faciles à trouver. Si vous estimez que la réduction en question nécessitera une conférence pour couvrir, alors cela ne correspond probablement pas au projet de loi, bien que je suis sûr qu'il pourrait y avoir des exceptions où l'idée de haut niveau est élégante et le diable dans les détails (pour le record, je ne suis pas sûr que je puisse penser à tout).

L'exemple que j'ai donné était délibérément simple et, espérons-le, quelque peu - sinon parfaitement - illustrant ces caractéristiques. La première fois que j'ai entendu parler de la coupe multiple, c'était dans une salle de classe, et notre instructeur a commencé par dire que non seulement c'est NP-dur en général, mais aussi NP-difficile lorsqu'il est limité aux arbres ... {pause dramatique} de hauteur un . Je me souviens ne pas avoir été en mesure de le prouver immédiatement, même si cela semble évident rétrospectivement.

Je suppose que rétrospectivement évident décrit de près ce que je recherche. Je ne sais pas si cela a quelque chose à voir avec la complexité de la description - il y a peut-être des situations où quelque chose d'apparemment trouble peut être qualifié d'élégant - n'hésitez pas à citer vos exemples (exceptions?), Mais j'apprécierais vraiment une justification. Étant donné qu'après un certain temps c'est une question de goût, vous devriez certainement vous sentir libre de trouver ce que je considère comme incroyablement complexe, parfaitement beau. J'ai hâte de voir une variété d'exemples!

Neeldhara
la source
1
Wiki de la communauté.
Dave Clarke
@supercooldave: Merci - je suppose que j'aurais dû le faire lors de la publication. Ma surveillance!
Neeldhara
@Jukka: Merci! Je pensais que c'était le montage de supercooldave. Je réalise maintenant que la modification a ajouté une balise. C'est maintenant une CW :)
Neeldhara
8
Peut-être que l'affiche devrait clarifier ce que l'on entend par «du livre». J'aurais pensé que (par analogie avec les preuves du livre) les algorithmes du livre sont tous courts, simples à énoncer, élégants et fonctionnent presque comme par magie. Cependant, l'autre thread a de nombreux messages avec des algorithmes incroyablement complexes qui ne satisfont à aucune des propriétés que j'ai mentionnées.
Robin Kothari
3
@Robin: les perceptions diffèrent. Je n'ai trouvé aucune des épreuves de "Épreuves du livre" simple (enfin, presque aucune). Et déjà la deuxième preuve (postulat de Bertrand) nécessite plusieurs pages, elles ne sont donc pas non plus courtes. - Inversement, je trouve que beaucoup d'algorithmes dans le fil associé sont assez simples (avec le recul, évidemment), et il est indéniable qu'ils sont courts.
Konrad Rudolph

Réponses:

9

Rabin montre le caractère unidirectionnel de (x ^ 2 mod N = pq) sans la factorisation de N par une réduction montrant que si vous pouvez prendre le module de racines carrées N = pq alors vous pouvez factoriser N.

Noam
la source
Une explication de cette réduction (si je ne me trompe pas) peut être trouvée à la page 7 de "La sécurité des systèmes cryptographiques: une enquête". Voici un lien: cs.yale.edu/publications/techreports/tr288.pdf
Neeldhara
9

En apprentissage automatique, il existe de nombreuses réductions intéressantes. Voici quelques exemples:

  • classification multiclasse en classification binaire ( lien ) - on peut résoudre un problème de choix parmi de nombreuses classes en résolvant des problèmes plus faciles de choisir entre deux.
  • apprentissage fort à apprentissage faible ( boosting ) - on peut atteindre des taux d'erreur arbitrairement bas étant donné la capacité à obtenir un peu mieux que aléatoire.
  • classement au classement ( lien )
  • perte quadratique de classification ( sondage ) - on peut estimer les probabilités d'appartenance à une classe en utilisant un classificateur avec un faible taux d'erreur.

Un tutoriel par Alina Beygelzimer, John Langford et Bianca Zadrozny en couvre d'autres.

Lev Reyzin
la source
2
Merci! Cela me semble le plus prometteur et aussi entièrement nouveau pour moi. Je devrais passer un peu de temps sur ce tutoriel et les autres références aussi.
Neeldhara
8

Théorème de Cook-Levin

Tout problème en NP peut être réduit en temps de polarité par une machine de turing déterministe à SAT. Pour référence, voir 1 .

Rui Ferreira
la source
8

Multiplication entière pour des transformations de Fourier rapides!

Jeffε
la source
6
et le corollaire: la correspondance des chaînes aux FFT!
Suresh Venkat
6

Théorème de Rice

Un de mes favoris. Il réduit le problème d'arrêt à n'importe quel ensemble d'index (ou son complément). Voir, par exemple, Sipser, problème 5.28.

Michaël Cadilhac
la source
1
La généralisation de Rice-Shapiro est encore plus belle. Voir l'exposition de Cutland: books.google.com/… )
Diego de Estrada
3

SAT à 3SAT

kk>3

Rui Ferreira
la source
3

3SAT à 3COL

Utiliser des gadgets pour réduire 3SAT au problème de décider si un graphique est colorable avec 3 couleurs. Pour référence, voir 1 .

Rui Ferreira
la source
1
La réduction en utilisant NAESAT au lieu de 3SAT (dans le livre de Papadimitriou) est plus directe.
Diego de Estrada le
3

Dans le sens de dire - oh c'était simple - rétrospectivement:

réduire le tri à un problème de coque convexe.

user200
la source
2

COUVERTURE EXACTE PAR 3 ENSEMBLES POUR SOUS-ENSEMBLE

U={1,2,,3m}S1,,SnUmU

w1,,wnKK

Si{0,1}3mn+1Siwi=jSi(n+1)3mjK=j=03m1(n+1)j

(Ma source était le livre de Papadimitriou.)

Diego de Estrada
la source