Algorithmes polynomiaux à grand exposant / constant

Connaissez-vous des algorithmes sensés fonctionnant en temps polynomial en (Longueur d’entrée + longueur en sortie), mais dont le temps de fonctionnement asymptotique dans la même mesure a un exposant / une constante vraiment énorme (au moins, où la limite supérieure prouvée du temps de fonctionnement est en de telle sorte)?

Les algorithmes basés sur le lemme de régularité sont de bons exemples pour les algorithmes polynomiaux à constantes terribles (soit dans l'exposant, soit comme coefficients directeurs).

Le lemme de régularité de Szemeredi vous indique que dans tout graphe sur sommets, vous pouvez les partitionner en ensembles dont les arêtes séparant des paires d'ensembles sont "pseudo-aléatoires" (les densités de sous-ensembles suffisamment grands ressemblent à des densités dans un graphe aléatoire). . Il est très agréable de travailler avec cette structure et, par conséquent, certains algorithmes utilisent la partition. Le problème est que le nombre d'ensembles dans la partition est une tour exponentielle dans le paramètre pseudo-aléatoire (voir ici: http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma ).$n$

Pour des liens vers des algorithmes qui reposent sur le lemme de régularité, voir par exemple: http://www.cs.cmu.edu/~ryanw/regularity-journ.pdf

Nouvelle de SODA 2013 : le problème de Max-Bisection peut être approché d’un facteur 0,877 en environ .$O(n^{10^{100}})$

Voici deux captures d'écran de Une approche axée sur l'énergie pour le déploiement des liaisons de Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben et James F. O'Brien, SOCG 2004:

Voici un résultat récent du papier FUN 2012, suspensions de tableaux d'Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph SB Mitchell, Ronald L. Rivest et Mihai Patrascu.

Nous montrons comment accrocher une image en enroulant une corde autour de n clous, en effectuant un nombre polynomial de torsions, de telle sorte que l’image tombe chaque fois que l’un des n clous est enlevé, et l’image reste suspendue lorsque moins de k clous sont supprimés.

Ne laissez pas le "nombre polynomial" vous tromper ... il s’avère être .$O(n^{43737})$

Il existe une classe de problèmes dont les solutions sont difficiles à calculer, mais il est facile de les approcher avec précision , dans la mesure où il existe des algorithmes polynomiaux pouvant approcher la solution à l'intérieur pour toute constante ε > 0. Cependant, il y a un problème: le temps d'exécution des approximateurs peut dépendre de assez mal, par exemple, être .1 / ϵ O ( n 1 / ϵ$(1+\epsilon)$$1/\epsilon$$O(n^{1/\epsilon})$

Voir plus d'informations ici: http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme .

Bien que l'exécution de tels algorithmes ait été améliorée par la suite, l'algorithme d'origine pour l'échantillonnage d'un point à partir d'un corps convexe avait le temps d'exécution .$\tilde{O}(n^{19})$

Dyer, Frieze et Kannan: http://portal.acm.org/citation.cfm?id=102783

Si est une logique modale tabulaire ou superintuitionniste, alors les systèmes de preuve de Frege étendus et de substitution de Frege pour sont polynômes et peuvent être interprétés de façon polynomiale dans EF classique (c'est le théorème 5.10 dans cet article ). L'exposant des simulations polynôme n'est pas explicitement indiqué dans le théorème 5.10, mais la preuve inductive du théorème donne , où est un cadre Kripke finie qui génère , de sorte qu'il peut soyez aussi gros que vous voulez selon la logique. (La situation empire dans le théorème 5.20.)L c c = 2 O ( | F | ) F $L$$L$$c$$c=2^{O(|F|)}$$F$$L$

Le meilleur algorithme actuellement connu pour reconnaître les graphiques cartographiques (une généralisation des graphiques plans) s’exécute en . Thorup, les graphiques de la carte en temps polynomial.$n^{120}$

Le calcul de l'équilibre du marché Arrow-Debreu prend calculs max-flow, où est l'utilité maximale. Duan, Mehlhorn, Un algorithme combinatoire polynomial pour le marché de la flèche linéaire-Debreu.$O(n^6\log(nU))$$U$

Problème de transitoire du tas de sable

Considérez le processus suivant. Prenez un carreau épais et déposez des particules de sable dessus, grain par grain. Un tas s'accumule progressivement, puis une grande partie du sable glisse des bords du carreau. Si nous continuons à ajouter des particules de sable, la configuration du tas se répète au bout d'un certain temps. Par la suite, la configuration devient récurrente, c’est-à-dire qu’elle revisite constamment un état vu plus tôt.

Considérez le modèle suivant pour le processus ci-dessus. Modélisez la mosaïque sous la forme d'une grille . Les particules de sable sont déposées sur les sommets de cette grille. Si le nombre de particules d'un sommet dépasse son degré, le sommet s'effondre et les particules qu'il contient se déplacent vers les sommets adjacents (en cascade). Une particule de sable qui atteint un sommet limite disparaît dans un évier («tombe»). Ceci est connu sous le nom de modèle de tas de sable abélien .$n \times n$

Problème: Combien de temps faut-il pour que la configuration soit récurrente en termes de , en supposant le pire algorithme pour la chute de particules de sable?$n$

Dans SODA '07 , László Babai et Igor Gorodezky ont prouvé que cette fois-ci étaient liés polynomial mais ..

Dans SODA '12 , Ayush Choure et Sundar Vishwanathan ont amélioré cette liaison à .$O(n^7)$

Cette réponse aurait semblé légèrement meilleure sans leur amélioration :)

Le problème du "crâne convexe" consiste à trouver le polygone convexe de surface maximale à l'intérieur d'un polygone simple donné. L'algorithme le plus rapide connu pour ce problème s'exécute en temps [Chang et Yap, DCG 1986].$O(n^7)$

La solution de Annihilation Games (Fraenkel et Yesha) a une complexité .$O(n^6)$

Il existe certains algorithmes non constructifs, notamment le théorème de Fellows et Langston et Courcelle .

En outre, l'algorithme de temps linéaire de Bodlaender pour la largeur d'arbre et le théorème de Courcelle sont notoirement impraticables.

Le théorème de Robertson-Seymour, alias Graph Minor Theorem, établit entre autres choses que pour tout graphe , il existe un algorithme qui détermine si un graphe arbitraire (de taille ) a comme mineur. La preuve est non constructive et la constante multiplicative (je pense non uniforme) est probablement si énorme qu'aucune formule ne peut être écrite explicitement (par exemple, en tant que fonction récursive primitive sur ).$G$$O(n^3)$$H$$n$$G$$G$

http://en.wikipedia.org/wiki/Graph_minor_theorem#Polynomial_time_recognition

Dans leur article ICALP 2014 , Andreas Björklund et Thore Husfeldt décrivent le premier algorithme polynomial (randomisé) qui calcule 2 chemins disjoints de longueur totale minimale (somme des deux chemins) entre deux paires de sommets donnés. Le temps d'exécution est en .$O(n^{11})$

Dans la partie 2 de la rectangulation Polygon: nombre minimal de gros rectangles , une modification pratique du problème de la partition du rectangle, motivée par les préoccupations de VLSI, est présentée:

Fat Rectangle Optimisation Problème: Étant donné un polygone orthogonal , maximiser le côté le plus court sur toutes rectangulations de . Parmi les partitions ayant le même , choisissez la partition contenant le moins de rectangles.$P$$\delta$$P$$\delta$

Pour le moment, seul un algorithme théorique existe, avec une durée d'exécution de . (Ce n'est pas une faute de frappe, et elle est obtenue grâce à une solution de programmation dynamique «naturelle» au problème qui y est énoncé.)$O(n^{42})$

Le calcul de la rigidité de la matrice [1] via la force brute / naïf / l'énumération prend apparemment un temps pour les matrices de taille éléments. cela peut être vu comme la limite convergente d’une suite d’estimations de plus en plus précises prenant , , , ... étapes. autrement dit, chaque estimation est exprimée en P-temps pour tout exposant arbitraire (c.-à-d. étapes). l'algorithme naïf choisit n'importe quel$O(2^n)$$n$$n \choose 1$$n \choose 2$$n \choose 3$$O(n^c)$$c$$n \choose c$$c$éléments de la matrice à modifier et tests pour la réduction des dimensions résultante. Cela n’a rien d’étonnant compte tenu du fait qu’il a été associé aux limites inférieures des circuits informatiques. Cela suit un modèle où de nombreux algorithmes ont une solution hypothétique de P-time pour certains paramètres, mais une preuve solide d'une limite inférieure impliquerait probablement ou quelque chose de plus fort.$\mathsf{P \neq NP}$

[1] Questions sur la rigidité de la matrice informatique

étonnamment l'une des réponses les plus évidentes n'a pas encore posté. la recherche d'une clique de taille (arêtes ou sommets) prend apparemment un temps par l'algorithme naïf / force brute qui énumère toutes les possibilités. ou plus précisément proportionnelle à étapes. (curieusement, cette donnée de base semble être rarement mentionnée dans la littérature.) Cependant, une preuve stricte de cela impliquerait . cette question est donc liée à la fameuse conjecture ouverte, qui lui est pratiquement équivalente. D'autres problèmes de type NP peuvent être paramétrés de cette manière.O ( n c ) ($c$$O(n^c)$ P≠N$n \choose c$$\mathsf{P \neq NP}$