Algorithmes polynomiaux à grand exposant / constant

59

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)?

Joris
la source
3
Voir mathoverflow.net/questions/65412 : "Le pire algorithme connu en termes de big-O ou plus précisément de big-Theta." J'ai posté une réponse là-bas.
Joseph O'Rourke
4
Il y a l'algorithme LOGSPACE de Reingold pour la connectivité (voir une question sur la complexité temporelle ), mais doutez que ce soit raisonnable dans le sens que vous voulez dire ici ...
Janne H. Korhonen,
1
@ Joseph ORourke: J'ai le papier "gros rectangle" sur mon bureau en ce moment!
Aaron Sterling
3
Bien que le soit un calcul légitime (la programmation dynamique le pousse), je l’ai inclus dans la version de la conférence comme une blague , une blague supprimée de la version du journal. n42
Joseph O'Rourke
9
La reconnaissance des graphes parfaits se trouve dans , et une avancée semble être nécessaire pour améliorer cela. O(|V(G)|9)
András Salamon,

Réponses:

39

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

Dana Moshkovitz
la source
2
Bon point! Cependant, je ne suis pas au courant d'un problème de calcul pour lequel il existe une limite inférieure correspondante de la tour des exponentielles. Gowers a prouvé une limite inférieure pour le lemme de régularité lui-même, mais je ne connais pas de problème de calcul où cela s'applique.
arnab
3
Je crois que les algorithmes de flocage décrits par Chazelle dans cet article ( arxiv.org/abs/0905.4241 ) ont une convergence optimale (c'est-à-dire une limite inférieure) qui est une tour de deux
Suresh Venkat le
Dans un article récent ( eccc.hpi-web.de/report/2014/018 ), je montre quelques autres algorithmes utilisant un lemme de régularité (arithmétique) qui ont d'énormes constantes cachées par la notation O ().
Arnn
55

Nouvelle de SODA 2013 : le problème de Max-Bisection peut être approché d’un facteur 0,877 en environ .O(n10100)

Jagadish
la source
54

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:

Corollaire 1. Le nombre d’étapes de notre algorithme est au maximum de $ 1752484608000 n ^ {79} L ^ {25} / D ^ {26} (\ Theta_0) $

Corollaire 2. Le nombre d'étapes dans notre algorithme est d'au plus $ 117607251220365312000 n ^ {79} (\ ell _ {\ max} / d _ {\ min} (\ Theta_0)) ^ {26} $]

Jeffε
la source
12
La constante est bien plus impressionnante que la puissance de :)n
Suresh Venkat
11
Ceci est un algorithme avec un exposant énorme ET une constante énorme ...
Hsien-Chih Chang
5
Les mêmes limites sont vraies pour Bubblesort.
Raphaël
1
À quel point ces limites sont-elles serrées?
Max
34

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(n43737)

Jagadish
la source
15
C'est (!!)(618)#gates in an AKS sorting network
Jeffε
23

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+ϵ)1/ϵO(n1/ϵ)

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

Sadeq Dousti
la source
17

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 .O~(n19)

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

Aaron Roth
la source
16

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 LLLcc=2O(|F|)FL

Emil Jeřábek
la source
16

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.n120

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.UO(n6log(nU))U

adrianN
la source
Je reçois une erreur de l'IEEE lorsque je suis votre lien, mais je suppose que vous vous référez au document FOCS'98 de Thorup "Cartographie des graphes en temps polynomial".
David Eppstein
1
Je veux dire ce papier, et ça me convient très bien.
adrianN
travaille pour moi depuis le U.
Suresh Venkat Le
12

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×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 ..

entrez la description de l'image ici

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

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

Jagadish
la source
11

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(n7)

Jeffε
la source
8

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 ).GO(n3)HnGG

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

aucun
la source
6

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(n11)

Lamine
la source
2

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δPδ

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(n42)

Thomas Klimpel
la source
-3

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 quelO(2n)n(n1)(n2)(n3)O(nc)c(nc)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.PNP

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

minute
la source
2
Je ne sais pas en quoi cela est différent (par exemple) d’essayer de trouver une clique max en énumérant tous les ensembles de taille k pour augmenter k. chaque pas est aussi p-time pour k fixe.
Suresh Venkat
oui, il est très similaire et me rappelle la conjecture de Hartmanis pour les ensembles de NP. même si la conjecture d'isomorphisme n'est pas vraie (le consensus actuel / la sagesse conventionnelle semble s'y opposer), il semble que les ensembles NP possèdent une propriété similaire mais sont peut-être un peu plus faibles, ce qui semble également nécessiter une recherche exhaustive
vzn
-4

é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 ) ( ncO(nc) PNP(nc)PNP

vzn
la source
2
1. il existe un algorithme (simple) qui améliore légèrement l'exposant. 2. Il s'agit d'une déclaration beaucoup plus forte que P non égal à NP, tout comme ETH est plus fort que P non égal à NP. Je pense que des algorithmes comme celui-ci n'ont pas été signalés car il semble que le PO ne soit pas intéressé par une recherche exhaustive d'algorithmes.
Sasho Nikolov
5
nitpicking: trouver une clique avec des arêtes peut être fait dans environ (car nous recherchons une clique avec sommets). n c O(ncO(c)
Daniel Marx
5
vous devez être prudent en supposant que tous les problèmes NP-complets ne peuvent être résolus que par la recherche par force brute. comme je l'ai dit, la multiplication matricielle peut accélérer la recherche d'une clique. pour de nombreux autres problèmes, nous avons des algorithmes temporels exponentiels exacts avec un meilleur exposant que la recherche par force brute. ce que vous parlez ressemble le plus à l'hypothèse de temps exponentielle: la conjecture (beaucoup plus forte que P neq NP) qui pour tout SAT nécessite temps où . k 2 s k n s k > 0k>2 k2sknsk>0
Sasho Nikolov
6
Il existe de nombreux cas où la recherche par force brute n'est pas optimale pour un problème NP-difficile. Trois exemples classiques: (1) Une couverture de vertex de taille peut être trouvée dans le temps, par exemple , (2) Un chemin de longueur peut être trouvé dans un temps similaire, (3) Un ensemble indépendant de taille dans un graphe planaire peut être trouvé dans le temps . BTW: Sur la question de l'ETH et la nécessité de la force brutale, vous pourriez trouver notre enquête intéressante: cs.bme.hu/~dmarx/papers/survey-eth-beatcs.pdf2 kn k k 2 O ( k2knkk2O(k)n
Daniel Marx
5
@vzn: est beaucoup plus rapide que . 2O(n)2O(n)2O(n)
Jeffε