Problèmes qui semblent exponentiels mais qui sont P

J'essaie de construire une liste d'algorithmes / problèmes qui sont "exceptionnellement utiles", comme dans la résolution de problèmes qui semblent "de nature très exponentielle", mais qui ont un algorithme particulièrement intelligent qui les résout finalement. Exemples de ce que je veux dire:

Programmation linéaire (L'algorithme simplex est un temps exponentiel; il a fallu beaucoup de temps pour trouver une solution temporelle polynomiale!)
Plus généralement, la programmation semi-définie
Test de primalité
2-SAT et HORNSAT
Déterminants informatiques (si cela ne semble pas difficile, pensez au permanent)
Trouver des correspondances parfaites
Une variété de problèmes théoriques de groupes durs qui peuvent être accomplis en utilisant la classification des groupes simples finis
Une variété de problèmes de graphes durs qui peuvent être accomplis en utilisant des caractérisations mineures interdites compliquées (intégration sur une surface arbitraire; délimitation de la largeur d'arbre et de la largeur de branche; graphiques réductibles Delta-Wye)
Calcul d'exponentielles dans un groupe borné (c.-à-d. Calcul d' en étapes, comme accompli par la mise au carré répétée) $a^b \mod k$ $\log b$
Calculs reposant sur l'algorithme LLL. (Cas particulier: algorithme euclidien. Cas plus général: algorithmes PSLQ ou HJLS.)
Problèmes de contraintes sans termes de Taylor (?). J'avoue que je ne comprends pas complètement cela, mais il semble que cela subsume probablement les cas 2-SAT / HORNSAT ci-dessus et toute algèbre linéaire sur des champs finis. Voir ici pour un article plus long
Problèmes calculables via des réductions holographiques .

En mention honorable, je mentionnerais également l'isomorphisme graphique, car il est toujours extrêmement facile ( ), et équivalent à tant d'autres problèmes d'isomorphisme: $n^{\log^2 n}$

Digraphes / multigraphs / hypergraphes (une sorte de problème «plus difficile»)
Automates finis / CFG

Évidemment, il y a une gamme de difficultés dans ces derniers, mais tous laissent au moins certaines personnes avec un certain sentiment de `` surprise '' dans le sens où le problème peut sembler difficile mais s'avérer traitable. LP peut sembler relativement simple, mais il a fallu un certain temps aux gens pour créer une solution réelle. La quadrature répétée ou la résolution de 2-SAT est quelque chose qu'un étudiant de premier cycle pourrait peut-être trouver seul, mais si vous n'aviez appris que des problèmes NP-Complete sans avoir vu HORNSAT, cela pourrait ressembler à un candidat naturel pour NP-Completeness. Résoudre le CFSG ou avoir un moyen polynomial pour vérifier la réductibilité Delta-Wye ne sont pas des exploits moyens.

J'espère que cela a du sens; il y a évidemment beaucoup d'attributs subjectifs ici, mais je suis curieux d'entendre ce que les autres trouvent comme des solutions efficaces à des problèmes "évidemment difficiles".

complexity-theory polynomial-time efficiency Alex Meiburg
la source

Comme motivation pour cette question (parce qu'un ami le demandait également): Nous parlons souvent de l'importance d'enseigner aux élèves la complétude et l'indécidabilité de NP, car cela les aide à reconnaître quand les problèmes seront trop difficiles et ils devraient les éviter. Cette liste serait «des problèmes que vous pourriez confondre avec NP-Complete mais que vous pouvez réellement résoudre». Non pas que je m'attende à ce que de nombreux étudiants soient pleins sous l'impression que les déterminants ne peuvent pas être calculés - tout comme ils ne rencontreront probablement pas 3SAT dans la nature - mais ils devraient reconnaître d'autres problèmes équivalents

Alex Meiburg

Je soupçonne que c'est trop large pour convenir à notre site. Demander une liste exhaustive de quelque chose ne ressemble pas au genre de question qui fonctionne bien ici. "Je suis curieux d'entendre ce que les autres trouvent ..." sonne comme le genre de question qui ne convient pas ici; consultez notre centre d'aide .

Je comprends, j'essayais de reconnaître la subjectivité de cette question, mais je pense que cette question est largement quelque chose sur laquelle les gens s'entendraient et tireraient des enseignements d'une discussion productive. Pour les questions qui ont le ton que je veux peut-être (bien que je connaisse un autre site), voir cstheory.stackexchange.com/questions/20930/… ou cstheory.stackexchange.com/questions/11119/… ?

Alex Meiburg

En outre, il n'est pas du tout clair de savoir ce qui "se sent" exponentiel à qui.

Raphael

Pour moi, tous les algorithmes classiques et les plus récents et les plus efficaces pour vérifier ou trouver un arbre couvrant minimum (MST) d'un graphe à pondération de bord connecté sont de bons candidats. Beaucoup de ces algorithmes sont répertoriés dans wikipedia .

À première vue, ce problème ressemble au problème du voyageur de commerce, l'un des rares problèmes NP-hard les plus connus. Plus étonnant, il existe des algorithmes linéaires pour vérifier un MST et de nombreux algorithmes quasi linéaires pour trouver un MST! En fait, l'un des problèmes ouverts les plus connus dans les algorithmes est de savoir s'il existe un algorithme linéaire déterministe pour trouver un MST dans les graphiques généraux. Il s'avère qu'il existe de riches structures et propriétés mathématiques et graphiques ainsi qu'une multitude d'applications pratiques associées au MST, ce qui en fait l'un des sujets les plus agréables et les plus extensibles du cours d'informatique. Pour une introduction complète légèrement dépassée mais très bien écrite, veuillez consulter le tutoriel de Jason Eisner .

John L.
la source

Problèmes qui semblent exponentiels mais qui sont P

Réponses: