Wiki définit Le temps polynomial comme jachère:
Un algorithme est dit à temps polynomial si son temps dexécution est limité par une expression polynomiale dans la taille de lentrée pour lalgorithme, cest-à-dire $ T (n) = O (n ^ k) $ pour une constante $ k $
I comprendre quen général, la différence entre Temps polynomial et Temps exponentiel est que la fonction exponentielle croît strictement plus vite que nimporte quelle fonction polynomiale, asymptotiquement ( référence ).
Jessaie de comprendre le noyau définition de Temps exponentiel .
- Quels éléments feront exécuter un algorithme dans Temps exponentiel ?
- Quel changement dois-je faire dans lexpression polynomiale pour le rendre Temps exponentiel ? (Par cela je fais référence à la définition de lalgorithme au début de la question)
Commentaires
- 1. Faites beaucoup de choses de façon exponentielle. 2. Utilisez le polynôme comme puissance dune base > 1.
- Je ne ' t comprendre votre deuxième question. Les polynômes sont des polynômes; les exponentielles sont des exponentielles. Demander ce que vous devez changer pour transformer un polynôme en exponentiel revient à demander ce que vous devez changer pour transformer un logarithme en cosinus.
- @DavidRicherby Y aura-t-il des fonctions temporelles exponentielles si P = NP? Comment définir une fonction temporelle exponentielle en termes dexpression polynomiale?
- Les fonctions exponentielles existeront certainement si P = NP. Il y a probablement encore des problèmes qui ' prendront un temps exponentiel même si P = NP, même si aucun ne vient immédiatement à lesprit. Une fonction exponentielle peut être définie en termes de polynôme, mais ce polynôme doit être infiniment long – vous pouvez rechercher les extensions de Taylor si vous ' y êtes intéressé.
- @ymbirtt Même la version la plus simple du théorème de hiérarchie des temps dit quil ny a pas dalgorithme de temps polynomial pour tout problème EXPTIME-complet. Cela ' est un résultat inconditionnel: il ne ' t dépend de lhypothèse que P $ \ neq $ NP.
Réponse
-
Il ny a pas de réponse facile pour celle-ci, bien quil y ait des signes à surveiller . Examiner chaque sous-ensemble possible dun ensemble, par exemple, est exponentiel – donc si javais un ensemble dentiers $ \ {x_1, …, x_n \} $, et que je voulais vérifier chaque sous-ensemble de ceux-ci pour voir sils totalisent à $ 0 $, je devrais considérer exactement $ 2 ^ n $ sous-ensembles, ce qui rend cette méthode exponentielle. Plusieurs pièges différents peuvent rendre un algorithme exponentiel, cependant, plutôt que de rechercher de grandes catégories, analysez les algorithmes au cas par cas.
-
Si un algorithme prend $ n ^ 2 $ pas pour se terminer, alors cest un polynôme. Sil faut $ 2 ^ n $ pas, cest exponentiel. La différence est la position du $ n $. Si quelque chose est $ O (n ^ m) $ pour $ n > 1 $, $ m > 0 $, alors cest « s polynôme en $ n $ pour $ m $ fixe, mais exponentiel en $ m $ pour $ n $ fixe.
Commentaires
- Attention. La fonction $ n ^ m $ isn ' t polynôme dans $ n $ sauf si $ m $ est une constante. Et, si $ m $ est une constante, il nest ' pas logique de dire que la fonction est exponentielle dans cette constante.
- Oui, vous ' vous avez raison. Je ' clarifierai cela.
Réponse
Souvent, vous obtenez un algorithme de force brute exponentielle lorsque vous considérez un problème et énumérez tout son espace de recherche. En général, vous pensez à des problèmes de sous-ensemble (dans SAT, vous choisiriez un sous-ensemble de variables définies sur true), des problèmes de permutation (dans TSP, chaque tour est une permutation des villes), et des problèmes de partition (dans la coloration du graphe, vous essayez de p artition des sommets en classes de couleurs). Ou pensez à trier même: il y a des permutations $ n! $ De $ n $ entiers. Parcourez chaque permutation et vérifiez si elle est triée. Idiot (et lent), mais ça marche.
Commentaires
- Notez cependant que $ O (n!) $ Est encore pire que $ O ( k ^ n) $. Si vous ' essayez toujours den savoir plus sur la complexité du temps, cela pourrait être une chose utile à vous prouver.