Principales raisons pour lesquelles les problèmes sont dans P ou BPP

Récemment, quand j'ai parlé à un physicien, j'ai affirmé que, selon mon expérience, lorsqu'un problème qui semble naïvement prendre un temps exponentiel se révèle non trivialement en P ou en BPP, il est généralement possible d'identifier une "raison primordiale" de la réduction. --- et presque toujours, cette raison appartient à une liste d’une dizaine de "suspects habituels" ou moins (par exemple: programmation dynamique, algèbre linéaire ...). Cependant, cela m’a alors amené à penser: pouvons-nous réellement écrire une liste décente de telles raisons? Voici une première tentative incomplète:

(0) Caractérisation mathématique. Problème a une caractérisation non purement mathématique «purement mathématique» qui, une fois connue, permet immédiatement de faire une recherche exhaustive sur une liste de poly (n) possibilités. Exemple: planarité de graphe, pour laquelle un algorithme O (n ⁶ ) découle du théorème de Kuratowski.

(Comme le souligne "planaire" ci-dessous, il s’agissait d’un mauvais exemple: même une fois que vous avez découvert une caractérisation combinatoire de la planarité, le fait de donner un algorithme polynomial en temps réel n’est toujours pas trivial. Laissez-moi vous substituer ici un meilleur exemple: , disons, "étant donné une entrée n écrite en binaire, calculez le nombre de couleurs nécessaires pour colorer une carte arbitraire incorporée sur une surface de n trous." Il n'est pas évident a priori qu'il s'agisse d'une machine calculable (ou même finie!). Mais il existe une formule connue qui donne la réponse, et une fois que vous connaissez la formule, il est trivial de calculer en temps polynomial. En attendant, la "réduction aux mineurs exclus / la théorie de Robertson-Seymour" devrait probablement être ajoutée en tant que raison principale distincte dans P.)

Quoi qu'il en soit, ce n'est pas précisément le genre de situation qui m'intéresse le plus.

(1) Programmation dynamique. Le problème peut être scindé de manière à permettre une solution récursive sans explosion exponentielle - souvent parce que les contraintes à satisfaire sont agencées dans un ordre simple ou linéaire. "Purement combinatoire"; aucune structure algébrique nécessaire. L'accessibilité des graphes (et donc 2SAT) est un cas particulier.

(2) les matroïdes. Problem a une structure matroid, permettant à un algorithme glouton de fonctionner. Exemples: correspondance, arbre couvrant minimal.

(3) algèbre linéaire. Le problème peut être réduit à la résolution d’un système linéaire, au calcul d’un déterminant, au calcul de valeurs propres, etc. On peut soutenir que la plupart des problèmes impliquant des "annulations miraculeuses", y compris celles résolvables par le formalisme de la porte d’allumette de Valiant, relèvent également du parapluie algébrique linéaire.

(4) la convexité. Le problème peut être exprimé comme une sorte d'optimisation convexe. La programmation semi-finale, la programmation linéaire et les jeux à somme nulle sont des cas particuliers (de plus en plus) spéciaux.

(5) Test d'identité polynomiale. Le problème peut être réduit à la vérification d’une identité polynomiale, de sorte que le théorème fondamental de l’algèbre mène à un algorithme aléatoire efficace - et dans certains cas, comme la primalité, même à un algorithme déterministe.

(6) Chaîne de Markov Monte Carlo. Le problème peut être réduit à l’échantillonnage à partir du résultat d’une marche à mélange rapide. (Exemple: compter approximativement les correspondances parfaites.)

(7) algorithme euclidien. GCD, fractions continues ...

Divers / Pas évident de savoir exactement comment classer: mariage stable, factorisation polynomiale, problème d'appartenance à des groupes de permutation, divers autres problèmes de théorie des nombres et de la théorie des groupes, problèmes de réseau de faible dimension ...

Ma question est la suivante: quelles sont les choses les plus importantes que j'ai laissées de côté?

Clarifier:

• Je me rends compte qu'aucune liste ne peut être complète: quel que soit le nombre fini de raisons que vous donniez, quelqu'un sera capable de trouver un problème exotique qui est dans P mais pas pour aucune de ces raisons. C'est en partie pour cette raison que je m'intéresse davantage aux idées qui posent beaucoup de problèmes différents, apparemment sans rapport, en P ou BPP, qu'aux idées qui ne fonctionnent que pour un problème.

• Je réalise aussi que la répartition des choses est subjective. Par exemple, les matroïdes ne devraient-elles être qu'un cas particulier de programmation dynamique? La solvabilité par recherche en profondeur d’abord est-elle assez importante pour constituer sa propre raison, distincte de la programmation dynamique? En outre, le même problème peut souvent se trouver dans P pour plusieurs raisons, en fonction de la façon dont vous le regardez: par exemple, trouver une valeur propre principale est dans P à cause de l'algèbre linéaire, mais aussi parce qu'il s'agit d'un problème d'optimisation convexe.

En bref, je ne souhaite pas de "théorème de classification" - mais juste une liste reflétant utilement ce que nous savons actuellement sur les algorithmes efficaces. Et c’est pourquoi ce qui m’intéresse le plus, ce sont les techniques permettant d’inscrire dans P ou BPP des éléments qui ont une large applicabilité mais qui ne correspondent pas à la liste ci-dessus - ou d’autres idées pour améliorer ma première tentative grossière de me vanter auprès du physicien.

Certaines classes de graphiques autorisent des algorithmes à temps polynomiaux pour les problèmes NP-difficiles pour la classe de tous les graphiques. Par exemple, pour les graphes parfaits, on peut trouver un plus grand ensemble indépendant en temps polynomial (grâce à vzn dans un commentaire pour faire du jogging dans ma mémoire). Cela permet également, via une construction de produit, d'expliquer de manière unifiée que plusieurs CSP apparemment tout à fait différents peuvent être traités (tels que ceux avec une structure arborescente qui sont généralement résolus par décomposition hiérarchique et la contrainte All-Different qui est habituellement résolue par un appariement parfait).

On pourrait faire valoir que les graphes parfaits sont "faciles" car ils permettent de belles formulations à programmation semi-finie des problèmes en question (et relèvent donc de l'algèbre linéaire et / ou de la convexité). Cependant, je ne suis pas sûr que cela rende complètement compte de ce qui se passe.

• András Z. Salamon et Peter G. Jeavons, Les contraintes parfaites sont traitables , CP 2008, LNCS 5202, 524–528. doi: 10.1007 / 978-3-540-85958-1_35

• Meinolf Sellmann, Le polytope des problèmes de satisfaction de contraintes binaires structurées en arborescence, CPAIOR 2008, LNCS 5015, 367–371. doi: 10.1007 / 978-3-540-68155-7_39

Comme l'a noté Gil Kalai, les propriétés des graphes qui forment des classes mineures peuvent être définies par un ensemble fini de mineurs interdits (c'est le théorème de Robertson-Seymour ). Un autre résultat de Robertson et Seymour est qu’il est possible de tester la présence d’un mineur en un temps cubique. Ensemble, ils conduisent à un algorithme polynomial pour déterminer les propriétés qui sont fermées.

• Neil Robertson et PD Seymour, Graph Minors. XIII. Le problème des chemins disjoints , Journal of Combinatorial Theory, série B 63 (1) 65-110, 1995. doi: 10.1006 / jctb.1995.1006

Un problème avec les propriétés de graphe mineur-fermé est qu'elles sont "petites"; exclure même un mineur exclut beaucoup de graphiques. C’est peut-être une des raisons pour lesquelles la décomposition structurelle de Robertson-Seymour fonctionne: il reste assez de graphiques pour qu’ils aient une belle structure.

• Serguei Norine, Paul Seymour, Robin Thomas et Paul Wollan, Les familles bien fermées du mineur sont petites , Journal of Combinatorial Theory, Série B 96 (5) 754–757, 2006. doi: 10.1016 / j.jctb.2006.01.006 ( pré-impression )

Une tentative pour aller au-delà des classes mineures est via des classes définies par des sous-graphes interdits ou des sous-graphes induits interdits.

Les propriétés de graphe définies par un ensemble fini de sous-graphes interdits ou induits sont décidables en temps polynomial, en examinant tous les sous-graphes possibles.

$F$$F$$F$$F$

$F$

$F$$F$$F$$F$

• Maria Chudnovsky et Paul Seymour, À l'exclusion des sous - graphes induits , Surveys in Combinatorics 2007, 99–119, Cambridge University Press, ISBN 9780521698238. ( pré-impression )

$F$$F$$F$

Réduction du treillis (algorithme LLL). C'est la base d'une factorisation polynomiale entière efficace et de certains algorithmes cryptanalytiques efficaces tels que la rupture de générateurs linéaires-congruentiels et RSA à faible degré. Dans un certain sens, vous pouvez considérer l'algorithme d'Euclidien comme un cas particulier.

Programmation d'entiers de Lenstra en dimension liée, algorithme de Lenstra-Lenstra-Lovasz et algorithmes ultérieurs associés - L'algorithme de Barvinok pour le nombre de solutions entières à un problème IP dans une dimension liée et l'algorithme P de Kannan pour le problème Frobenius / Sylvester peuvent être ajoutés comme une catégorie spéciale. Un problème non négligeable à résoudre ici consiste à trouver un algorithme P pour les problèmes d'ordre supérieur dans la hiérarchie de Presburger.

Une autre classe d’algorithme-P qui mérite d’être mentionnée est celle de l’algorithme-P attribué à un objet dont l’existence est prouvée par des preuves aléatoires. Exemples: algorithmes pour applications du lemma de Lovasz-Local; les versions algorimic du résultat de discordance de Spencer; (de saveur légèrement différente) des versions algorithmiques du lemme de régularité de Szemeredi.

Il existe un corpus théorique important et toujours croissant sur les classes de problèmes de satisfaction de contraintes de gabarit fixe qui utilisent des algorithmes à temps polynomiaux. Une grande partie de ce travail nécessite la maîtrise du livre de Hobby et MacKenzie , mais heureusement pour ceux d'entre nous qui s'intéressent plus à l'informatique qu'à l'algèbre universelle, certaines parties de cette théorie ont été suffisamment simplifiées pour être accessibles à un public de TCS.

$\Gamma$$S$$T$$\Gamma$$S$$T$

$\Gamma$$k \ge 3$$k$$\Gamma$$(0,0,\dots,0)$$S$$0$$T$

$\Gamma$$\Gamma$$\Gamma$$\Gamma$; cela signifie en pratique que la classe de problèmes contient tous les sous-problèmes successivement plus simples considérés par un résolveur de contraintes, de sorte que le processus de résolution de contraintes évite de générer des instances intermédiaires "difficiles" tout en résolvant des problèmes "faciles".

$\Gamma$$\Gamma$

Les résultats obtenus à ce jour semblent indiquer qu’il devrait exister une sorte de transformation d’alimentation générale d’un espace d’état d’atteignabilité sous-jacent, capable de transformer de tels problèmes en problèmes ayant un tuple constant dans chaque relation, comme dans l’exemple ci-dessus. (Ceci est mon interprétation personnelle de la recherche en cours et pourrait bien être complètement faux , selon la façon dont la recherche en cours pour un algorithme pour les algèbres avec des termes cycliques casseroles, donc je réserve le droit d'abjurer cela.) On sait que quand il ISN 't une telle transformation alors le problème est NP-complet. La frontière de la conjecture de dichotomie implique actuellement de combler cette lacune; voir la liste des problèmes en suspens de l'atelier de 2011 sur l'algèbre et les CSP .

Dans les deux cas, cela mérite probablement une entrée dans la liste de Scott.

Une seconde classe dans PTIME permet d'appliquer des techniques de cohérence locale pour élaguer les solutions possibles, jusqu'à ce qu'une solution soit trouvée ou qu'aucune solution ne soit possible. Ceci est essentiellement une version sophistiquée de la façon dont la plupart des gens résolvent les problèmes de Sudoku. Je ne pense pas que cette raison figure actuellement dans la liste de Scott non plus.

$\Gamma$

Enfin, il y a aussi un travail passionnant initié par Manuel Bodirsky pour le cas des domaines infinis. Certains algorithmes semblent assez étranges et pourraient éventuellement conduire à plus d'entrées dans la liste de Scott.

Je vois que Chandra y a fait allusion, mais je pense que la structure d'une relaxation LP (due par exemple à une unimodularité totale) est une forme omniprésente de "structure" qui conduit à la polynomialité. Cela représente une grande classe d'algorithmes poly-temps. Si l’on inclut les problèmes de promesse, cela représente également une grande classe d’algorithmes d’approximation. Les catégories de raisons les plus fréquentes que l’on ne rencontre pas dans les disques et / ou les SDP sont l’élimination gaussienne et la programmation dynamique. Il existe bien sûr d’autres, comme les algorithmes holographiques, qui n’ont pas d’explications simples.